剑指 Offer 03. 数组中重复的数字
题目：
在一个长度为 n 的数组nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
题解：
遍历数组，将数据存储在map中，每次循环均判断map中是否存在：
-若存在，则直接break，返回结果；
-若不存在，则将数据存储在map集合中继续遍历。
public int findRepeatNumber(int[] nums) {
Map map = new HashMap();int i=0;for (i=0;i<nums.length;i++){
if (map.containsKey(nums[i])){
break;}else {
map.put(nums[i],i);}}return nums[i];}
剑指 Offer 53 - I. 在排序数组中查找数字 I
题目：
统计一个数字在排序数组中出现的次数。
题解1：
- 定义
helper1函数，返回target值最后一次出现的下标； - 判断条件为
nums[mid]<=tar，即不断的将low值右移，返回low值。
public int search(int[] nums, int target) {
return helper1(nums, target) - helper1(nums, target - 1);}int helper1(int[] nums, int tar) {
int low = 0, high = nums.length - 1;while(low <= high) {
int mid = (low + high) / 2;if(nums[mid] <= tar) low = mid + 1;else high = mid - 1;}return low;}
题解2：
- 定义
helper2函数，返回target值第一次出现的下标； - 判断条件为
nums[mid]>=tar，即不断的讲high值左移，返回high值。
public int search(int[] nums, int target) {
return helper1(nums, target+1) - helper1(nums, target);}int helper2(int[] nums, int tar) {
int low = 0, high = nums.length - 1;while(low <= high) {
int mid = (low + high) / 2;if(nums[mid] >= tar) high = mid - 1;else low = mid + 1;}return high;}
剑指 Offer 53 - II. 0～n-1中缺失的数字
题目：
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
题解1：
等差数列求和sum1减去数组之和sum2
public int missingNumber(int[] nums) {
int sum1 = (nums.length)*(nums.length+1)/2;int sum2=0;for (int i = 0;i<nums.length;i++){
sum2=sum2+nums[i];}return sum1-sum2;}
题解2：
返回数组元素nums[i]和i不相等的下标i
public int missingNumber(int[] nums) {
int len = nums.length;for (int i = 0; i < len; i++) {
if (i != nums[i]) return i;}return len;}
34. 在排序数组中查找元素的第一个和最后一个位置
题目：
给定一个按照升序排列的整数数组nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]
题解：
- 利用剑指 Offer 53 - I. 在排序数组中查找数字 I 中
helper1和helper2函数分别得到结束位置和开始位置; - 特殊处理一下数组中不存在目标值 target的情况：利用内置二分查找函数
Arrays.binarySearch(nums,target)，若小于0则代表有序数组中不存在该值，返回[-1,-1]。
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];if (Arrays.binarySearch(nums,target)>=0){
res[1] = helper1(nums, target)-1;res[0] = helper2(nums, target)+1;} else {
res[0] = -1;res[1] = -1;}return res;}
int helper1(int[] nums, int tar) {
int low = 0, high = nums.length - 1;while (low <= high) {
int mid = (low + high) / 2;if (nums[mid] <= tar) low = mid + 1;else high = mid - 1;}return low;}
int helper2(int[] nums, int tar) {
int low = 0, high = nums.length - 1;while (low <= high) {
int mid = (low + high) / 2;if (nums[mid] >= tar) high = mid - 1;else low = mid + 1;}return high;}
暴风雨结束后，你不会记得自己是怎样活下来的，你甚至不确定暴风雨是否真的结束了。但有一件事是确定的:当你穿过了暴风雨，你早已不再是原来那个人。