二分查找

要求：排序数组
写法：左闭又闭
复杂度为log时考虑二分

  1.     int left = 0, right = nums.length - 1;
  2.     int mid = right / 2;
  3.     while (left <= right) {
  4.         if (nums[mid] == target) return mid;
  5.         else if (nums[mid] > target) {
  6.             right = mid - 1;
  7.             mid = (left + right) / 2;
  8.         }
  9.         else {
  10.             left = mid + 1;
  11.             mid = (left + right) / 2;
  12.         }
  13.     }

找平方根

  1. class Solution {
  2.     public int mySqrt(int x) {
  3.         int l = 0, r = x, ans = -1;
  4.         while (l <= r) {
  5.             int mid = (l + r) / 2;
  6.             if ((long) mid * mid <= x) {
  7.                 ans = mid;
  8.                 l = mid + 1;
  9.             } else {
  10.                 r = mid - 1;
  11.             }
  12.         }
  13.         return ans;
  14.     }
  15. }

双指针

快慢指针

27. 移除元素

  1. class Solution {
  2.     public int removeElement(int[] nums, int val) {
  3.         int slowIndex = 0, fastIndex = 0;
  4.         int size = nums.length;
  5.         for ( ; fastIndex < size; ++fastIndex) {
  6.             if (nums[fastIndex] != val) {
  7.                 nums[slowIndex] = nums[fastIndex];
  8.                 slowIndex++;
  9.             }
  10.         }
  11.         return slowIndex;
  12.     }
  13. }

左右指针

977. 有序数组的平方

  1. class Solution {
  2.     public int[] sortedSquares(int[] nums) {
  3.         int left = 0, right = nums.length - 1;
  5.         int[] res = new int[nums.length];
  6.         int flag = right;
  7.         for (int i = 0; i <= right; ++i) {
  8.             nums[i] *= nums[i];
  9.         }
  10.         while (flag >= 0) {
  11.             if (nums[left] > nums[right]) {
  12.                 res[flag] = nums[left];
  13.                 flag--;
  14.                 left++;
  15.             }
  16.             else {
  17.                 res[flag] = nums[right];
  18.                 flag--;
  19.                 right--;
  20.             }
  21.         }
  22.         return res;
  23.     }
  24. }

滑动窗口

两个循环，外层右指针，内层滑动窗口

209. 长度最小的子数组

内层 本题窗口中的数要大于等于target

  1. class Solution {
  2.     public int minSubArrayLen(int target, int[] nums) {
  3.         int slow = 0, fast = 0;
  4.         int len = nums.length;
  6.         int sum = 0;
  7.         int res = Integer.MAX_VALUE;
  8.         while (fast < len) {
  9.             sum += nums[fast];
  10.             while (sum >= target) {
  11.                 res = Math.min(res, fast - slow + 1);
  12.                 sum -= nums[slow];
  13.                 slow++;
  14.             }
  15.             fast++;
  16.         }
  17.         return res == Integer.MAX_VALUE ? 0 : res;
  18.     }
  19. }

904. 水果成篮

内层 本题窗口中水果种类不能大于2