数组

其实我们最常见的就是数组相关的问题，如：

1. 排序：选择排序、插入排序、归并排序、快速排序等

2. 查找：二分查找法

3. 数据结构：堆、栈、队列等

LeetCode704. 二分查找

二分查找用于在有序数组中查找目标值：

class Solution {
    public static int binarySearch(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        // 循环不变量：在区间 [left, right] 中寻找目标值
        int left = 0;
        int right = arr.length - 1;
        int mid = -1;
        while (left <= right) {
            mid = left + (right - left) / 2; // 不要用 (left + right) / 2 计算中间值，存在整型溢出问题
            System.out.println("left=" + left + ", right=" + right + ", mid=" + mid);
            if (target == arr[mid]) {
                return mid;
            } else if (target < arr[mid]) {
                right = mid - 1; // 目标值在区间 [left, mid - 1] 中
            } else {
                left = mid + 1; // 目标值在区间 [mid + 1, right] 中
            }
        }
        return -1;
    }
}

https://leetcode.cn/problems/binary-search

LeetCode283. 移动零

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        // 循环不变量：区间 [0, nonZero) 中都是非零元素
        int nonZero = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                if (nums[nonZero] == 0) {
                    swap(nums, i, nonZero++);
                } else {
                    nonZero++;
                }
            }
        }
    }

    private void swap(int[] nums, int one, int another) {
        int tmp = nums[one];
        nums[one] = nums[another];
        nums[another] = tmp;
    }
}

https://leetcode.cn/problems/move-zeroes

LeetCode75. 颜色分类

class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int red = 0;
        int blue = nums.length - 1;
        // 循环不变量：[0, red) 中是红色元素，[red, blue] 中是白色元素，则 (blue, nums.length) 中是蓝色元素
        for (int i = 0; i <= blue;) {
            if (nums[i] == 1) { // 白色
                i++;
            } else if (nums[i] == 0) { // 红色
                swap(nums, i, red++);
                i++;
            } else { // 蓝色
                swap(nums, i, blue--);
            }
        }

    }

    private void swap(int[] nums, int one, int another) {
        int tmp = nums[one];
        nums[one] = nums[another];
        nums[another] = tmp;
    }
}

https://leetcode.cn/problems/sort-colors

LeetCode167. 两数之和II - 输入有序数组

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (nums == null || nums.length < 2) {
            throw new RuntimeException("no solution");
        }
        // 数组有序，可以使用对撞指针
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            if (numbers[left] + numbers[right] == target) {
                return new int[] {++left, ++right};
            } else if (numbers[left] + numbers[right] < target) {
                left++;
            } else {
                right--;
            }
        }
        throw new RuntimeException("no solution");
    }
}

https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted

LeetCode209. 长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int numsLen = nums.length;
        int minLen = numsLen + 1; // 初始化为不可能的长度
        int left = 0, right = -1; // [left, right] 是滑动区间
        int sum = 0; // nums[left, right] 子数组的元素和
        while (left < numsLen) {
            if (sum < target && right < numsLen - 1) {
                sum += nums[++right];
            } else {
                sum -= nums[left++];
            }
            if (sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
            }
        }
        return (minLen == numsLen + 1) ? 0 : minLen;
    }
}

https://leetcode.cn/problems/minimum-size-subarray-sum

LeetCode3. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] freq = new int[128]; // 字符的 ascii 值 -> 字符出现频率
        int maxLen = 0; // 最长子串的长度
        int left = 0, right = -1; // [left, right] 是滑动区间
        while (left < s.length()) {
            if (right < s.length() - 1 && freq[s.codePointAt(right + 1)] == 0) { // 当前区间 [left, right] 中不存在 right 右边的这个元素
                freq[s.codePointAt(++right)]++;
            } else {
                freq[s.codePointAt(left++)]--;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

https://leetcode.cn/problems/longest-substring-without-repeating-characters