快慢指针

数组问题中常见的快慢指针技巧，是让你原地修改数组
26. 删除有序数组中的重复项
让慢指针slow走后面，快指针fast走前面探路，找到一个不重复的元素就赋值给slow并让slow向前走一步。这样就保证nums[0..slow]都是无重复元素。
前提是数组已经排序，所以重复的元素一定连在一起。

class Solution {
    public int removeDuplicates(int[] nums) { 
        int slow = 0;
        int fast = 0;
        while(fast < nums.length) {
            if (nums[slow] != nums[fast]) {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;
    }
}

除了在有序数组中去重，题目还能要求对数组中的某些元素进行原地删除
27. 移除元素
慢指针slow在后面，快指针fast在前面探路，当nums[fast] == val时，fast++，否则就赋值给slow指针，并且slow++。
快指针负责探路，根据题目要求完成相应判断操作。
慢指针负责收集符合条件的元素。

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        int fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}

283. 移动零
先用快慢指针原地把数组的中零元素给删除，然后把后面的元素都赋值为零。

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        int fast = 0;

        while (fast < nums.length) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }

    }
}

双指针

167. 两数之和 II - 输入有序数组
只要数组有序，就应该想到双指针。
通过调节左、右指针就可以调整sum的大小。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (right > left) {
            int sum = numbers[right] + numbers[left];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum > target) {
                right--;
            } else if (sum < target) {
                left++;
            }
        }
        return new int[]{-1, -1};

    }
}

344. 反转字符串
双指针一个在头、一个在尾，向中间移动移动过程中交换元素。
需要一个临时变量存交换的值。

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        char temp = 'a';

        while (left < right) {
            temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

前缀和

前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。

一维数组中的前缀和

303. 区域和检索 - 数组不可变

class NumArray {

    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
    }

    public int sumRange(int left, int right) {
        int res = 0;
        for (int i = left; i <= right; i++) {
            res += nums[i];
        }
        return res;
    }
}

这样，可以达到效果，但是效率很差，因为 sumRange 方法会被频繁调用，而它的时间复杂度是 O(N)，其中 N 代表 nums 数组的长度。
这道题的最优解法是使用前缀和技巧，将 sumRange 函数的时间复杂度降为 O(1)，说白了就是不要在 sumRange 里面用 for 循环，咋整？
直接看代码实现：

class NumArray {
    // 前缀和数组
    private int[] preSum;

    /* 输入一个数组，构造前缀和 */
    public NumArray(int[] nums) {
        // preSum[0] = 0，便于计算累加和
        preSum = new int[nums.length + 1];
        // 计算 nums 的累加和
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }

    /* 查询闭区间 [left, right] 的累加和 */
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

二维数组中的前缀和

304. 二维区域和检索 - 矩阵不可变
二维的前缀和数组如何构造

class NumMatrix {
    // 定义：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
    private int[][] preSum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        if (m == 0 || n == 0) return;
        // 构造前缀和矩阵
        preSum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 计算每个矩阵 [0, 0, i, j] 的元素和
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];
            }
        }
    }

    // 计算子矩阵 [x1, y1, x2, y2] 的元素和
    public int sumRegion(int x1, int y1, int x2, int y2) {
        // 目标矩阵之和由四个相邻矩阵运算获得
        return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
    }
}

如何计算sumRegion

差分

二分搜索

寻找一个数（基本的二分搜索）

此方法仅仅局限于「在有序数组中搜索指定元素」这个基本场景
704. 二分查找

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; //注意

        while (left <= right) { //注意
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1; //注意
            } else if (nums[mid] > target) {
                right = mid - 1; //注意
            }
        }

        return -1;
    }
}

寻找右侧边界(左侧边界)的二分查找

此方法仅仅局限于「在有序数组中搜索指定元素」这个基本场景
34. 在排序数组中查找元素的第一个和最后一个位置
本题需要找到右侧边界和左侧边界

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return right;
}

LeetCode

数组（lubuladong）