题一：二分查找法-Java：用于有序数组
//实验数据
int[] arr = {3,21,34,46,55,71,74,80,97};
代码：
public int findIndex(int value, int[] arr) {
// arr是有序数组
// value是目标值
int min = 0; //最大值，最小值的索引值
int max = arr.length - 1;
int mid = (min + max) / 2;
while (arr[mid] != value) {
if (arr[mid] > value) {
max = mid - 1;
} else if (arr[mid] < value) {
min = mid + 1;
}
mid = (min + max) / 2;
if (min > max) return -1;//如果最小索引大于最大索引证明没有找到这个value，要退出循环
}
return mid;//返回索引
}
题二：给定一个数组，写一个函数，将数组中的0都挪到数组的末尾，而维持其他非0元素的相对位置
//实验数据
int[] nums = {0,1,0,3,12};
//排序后
nums = {1,3,12,0,0}
思路：将所有非0元素拿出来，放在按顺序放在一个数组中，然后将最后的位置全部塞进0
public ArrayList moveZero(int[] nums) {
ArrayList arrayList = new ArrayList();
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
arrayList.add(nums[i]);
}
}
int diff = nums.length - arrayList.size();
if (diff == 0) {
return arrayList;
} else {
for (int i = 0; i < diff; i++) {
arrayList.add(0);
}
return arrayList;
}
}
思路二：遍历所有数组，将非0元素都放在前K位，剩余的都填充0
public int[] moveZero2(int[] nums) {
int k = 0;//在数组nums中，[0...k) 均为非0元素
//思路：在遍历的[0...i]个元素的数组中，所有的非0元素都按照顺序在[0...k)中
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) { //如果是非0元素，将该元素放在k位置
nums[k] = nums[i];
k++; //k++
}
}
//将剩余位置，都放置为0
for (int i = k; i < nums.length; i++) {
nums[i] = 0;
}
return nums;
}
题目三：给n个元素的数组，元素取值只有0，1，2三种可能，请为这个数组进行排序
思路一：使用计数排序，适用于元素个数非常有限的情况。遍历数据0，1，2的分别的元素个数，然后按照数值大小，在对应的位置分别放置多少个元素即可
public int[] sortColors(int[] nums) {
int[] counts = {0, 0, 0};
// 遍历数组，查出数值个数
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
counts[0]++;
} else if (nums[i] == 1) {
counts[1]++;
} else if (nums[i] == 2) {
counts[2]++;
} else {
return null;
}
}
int index = 0;
for (int i = 0; i < counts.length; i++) { //按照顺序塞入值
for (int j = 0; j < counts[i]; j++) {
nums[index] = i;
index++;
}
}
return nums;
}
思路二：三路快排，只需遍历一次即可: 将数组分为三部分，第一部分全是0 ，第二部分全是1，第三部分全是2。对第二部进行遍历：如果值=1，则往后遍历一位；如果值=2，将第三部分的左侧边界往左移动一位，并将i和左侧边界值交换位置(放在第三部分的最前端)，i的值不变；同理，如果值=0，将第一部分的右侧值往右移动一位，并将i和右侧边界交换位置，(放在第一部分的最右端)，i的值不变
public int[] sortColors2(int[] nums) {
// 分为三部分，第一部分全是0 ，第二部分全是1，第三部分全是2
//初始化索引值
int zero = -1;//nums[0,zero] 第一部分
int two = nums.length;//nums[two,length-1] 第三部分
for (int i = 0; i < two; ) {
if (nums[i] == 1) {
i++;
} else if (nums[i] == 2) {
two--; //第三部分的左侧边界，往左减一位
swap(nums, two, i); //将i和two交换位置
} else if (nums[i] == 0) {
zero++; //第一部分的右侧边界，往右加一位
swap(nums, zero, i);
} else {
return null;
}
}
return nums;
}
// 交换数组元素
public static void swap(int[] array, int x, int y) {
int xx = array[x];
int yy = array[y];
array[x] = yy;
array[y] = xx;
}
题四：在n长度的数组中，找到第k大的数值
题五：给定一个有序整型数组和整型数target，在数组中找两个元素，使其相加和为target，并返回开两个元素的索引
int[] nums = {2,7,11,15};
int target = 9;
//结果返回的索引就是：1，2(索引从1开始算)
思路：使用二分查找，nums[i] 在剩余数组(也是有序的)中，寻找target-nums[i] (每一次遍历，都使用一次二分查找)
思路二：对撞指针，(双指针)一个指针在数组首，一个指针在数组尾，两个指针不停的往中间移动 O(n)
public int[] twoSum(int[] arr, int target) {
if (arr.length < 2) return null;
int l = 0;
int r = arr.length - 1;
int res[] = {0, 0};
while (l < r) {
if ((arr[l] + arr[r]) == target) {
res[0] = l + 1;
res[1] = r + 1;
return res; //返回索引数组
} else if ((arr[l] + arr[r]) < target) {
l++; //最左侧往右移一位
} else {
r--; //最右侧往左移一位
}
}
throw null; //如果没有找到，抛出异常
}
题六：给定一个数组和数字s，找到数组中的最短连续子数组，使得连续子数组的数字和sum>=s，返回这个最短子数组的长度
//实验数据
int[] nums={2,3,1,2,4,3};
int s = 7;
//输出结果：子数组[3,4]，长度为2
思路：滑动窗口,子数组[l,r]，当子数组的和<s时，将子数组的右侧往右移动，子数组增加一位；当子数组的和>=s时，将子数组的左侧往右移一位，子数组减少一位。
public int minSubArr(int[] nums, int s) {
int l = 0, r = -1; //nums[l...r]是我们的滑动窗口
int sum = 0;
int res = nums.length + 1;
while (l < nums.length) { //左边界 < 长度
if (r + 1 < nums.length && sum < s) { //当前窗口的和 <s
r++; //将右边界，往右移动，增加一位
sum += nums[r];
} else {
l++; //将左边界，往右移动，减少一位
sum -= nums[l];
}
if (sum >= s) {
res = min(res, r - l + 1);
}
}
if (res == nums.length + 1) { //如果没有，则返回0
return 0;
}
return res;
}
//求最小值
public int min(int i, int j) {
if (i < j) {
return i;
} else {
return j;
}
}
题七：寻找字符串中，没有重复字母的最长子字符串
//示例数据：
"abcabcbb" -> "abc"
"nnnnn" -> "n"
"pwwkew" -> "wke"
思路：滑动窗口 ，滑动窗口的长度并不是固定不变的。每次对比下一个字符是否出现在子字符串时，使用一个频率数组，记录每个字符在子字符串中出现的频率。如果为0，那就代表没有在子字符串中出现过；如果非0，就代表出现过