> 数组类问题一般可优化为O(n)复杂度的问题
> 常用技术
- 快慢指针滑动
- 首尾指针对撞
[toc]
最大连续1的个数
LeetCode485
① [暴力] 单次遍历，连续1直到末位情况需再次计算
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0;
int cnt = 0;
for (int item : nums) {
if (item == 1) ++cnt;
else {
max = max > cnt ? max : cnt;
cnt = 0;
}
}
return max > cnt ? max : cnt;
}
② [双指针] 慢指针指向1子串首元素，快指针指向1子串末元素下一元素，差为数目
public int findMaxConsecutiveOnes(int[] nums) {
int slow = 0;
int fast = 0;
int max = 0;
while (fast < nums.length) {
if (nums[fast] == 0) {
max = Math.max(max, fast - slow);
slow = ++fast;
}
else ++fast;
}
return Math.max(max, fast - slow);
}
反转字符串
LeetCode344
[双指针]
public void reverseString(char[] s) {
int slow = 0;
int fast = s.length - 1;
char tmp;
while(slow < fast) {
tmp = s[fast];
s[fast--] = s[slow];
s[slow++] = tmp;
}
}
数组拆分
LeetCode561
① [转义] 每个min对中相差最小即两两相邻可使和最大，排序后挑选即可
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length; i += 2)
sum += nums[i];
return sum;
}
② [★] 待续
两数之和
已知被减数，遍历指向的当前减数，可计算另一减数
必须第二次遍历或额外内存寻找另一减数下标
① [暴力求解] 每次遍历第一减数，并从此向后寻找零一减数，直到满足条件返回下标
public static int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length - 1; i++)
for (int j = i + 1; j < nums.length; j++)
if (nums[i] + nums[j] == target)
return new int[]{i, j};
return null;
}
② [两次遍历] 哈希表是高效查找算法，第一次遍历存储第一减数下标，第二次遍历通过计算出该数查找下标，注意排除拿到同一下标情况
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++)
map.put(nums[i], i);
for (int i = 0; i < nums.length; i++) {
int key = target - nums[i];
if (map.containsKey(key) && map.get(key) != i)
return new int[]{i, map.get(key)};
}
return null;
}
③ [一次遍历] 查找当前数是否为已计算结果
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i]))
return new int[]{map.get(nums[i]), i};
map.put(target - nums[i], i);
}
return null;
}
两数之和 – 有序数组
[双指针] 利用排序性质，首指针足够小，尾指针足够大，要么解唯一，要么无解
public static int[] twoSum(int[] nums, int target) {
int h = 0;
int t = nums.length - 1;
while(h < t) {
int s = nums[h] + nums[t];
if (s == target) return new int[] {h + 1, t + 1};
else if (s < target) h++;
else t--;
}
return null;
}
买卖股票的最佳时机
LeetCode121
[双指针]
public static int maxProfit(int[] prices) {
int slow = 0;
int fast = 1;
int temp = 0;
int max = 0;
while (fast < prices.length) {
if (prices[slow] > prices[fast])
slow = fast;
else {
temp = prices[fast] - prices[slow];
max = max > temp ? max : temp;
}
fast++;
}
return max;
}
判断子序列
LeetCode392
[双指针] 依次遍历两字符串下标匹配，O(n)复杂度
public boolean isSubsequence(String s, String t) {
int index = -1;
for (char c : s.toCharArray()) {
index = t.indexOf(c, index + 1);
if (index == -1) return false;
}
return true;
}
移动零
LeetCode283
① [暴力] 从零开始到最后一个非零数依次前移去除所夹0，末位补0
public static void moveZeroes(int[] nums) {
int head = 0;
int tail = nums.length - 1;
while (nums[tail] == 0)
if (tail > 0) tail--;
else return;
while (head < tail) {
while (nums[head] == 0) {
for (int cur = head; cur < tail; cur++)
nums[cur] = nums[cur + 1];
nums[tail] = 0;
tail--;
}
head++;
}
}
② [改进] 第一次遍历筛选出非零数，第二次遍历将非零数依次填值，剩余置零
public void moveZeroes(int[] nums) {
int len = nums.length;
List<Integer> list = new ArrayList<>(len);
for (int i = 0; i < len; i++)
if (nums[i] != 0) list.add(nums[i]);
for (int i = 0; i < list.size(); i++)
nums[i] = list.get(i);
Arrays.fill(nums, list.size(), len, 0);
}
③ [改进] 快指针筛选非零数，慢指针依次填入非零数，快指针遍历完后其余填零
public static void moveZeroes(int[] nums) {
int slow = 0;
int fast = 0;
for (; fast < nums.length; fast++)
if (nums[fast] != 0) nums[slow++] = nums[fast];
for(; slow < nums.length; slow++)
nums[slow] = 0;
}
④ [改进] 慢指针找到首个零项，快指针从慢指针出发找到第一个非零项，值交换
public static void moveZeroes(int[] nums) {
int slow = 0;
int fast = 0;
while (fast < nums.length) {
if (nums[slow] != 0) fast = ++slow;
else {
if (nums[fast] == 0) fast++;
else {
nums[slow] = nums[fast];
nums[fast] = 0;
}
}
}
}
⑤ [改进] 慢指针记录首个0与其后快指针记录的首个非零数交换，慢指针依次填值，首位非零值与自身交换位置不动
public static void moveZeroes(int[] nums) {
int slow = 0;
int fast = 0;
for (; fast < nums.length; fast++)
if (nums[fast] != 0) {
int temp = nums[slow];
nums[slow++] = nums[fast];
nums[fast] = temp;
}
}
移除元素
LeetCode27
① [迁移] 相当于移动零问题，slow所指即为除去该值数组末尾
public int removeElement(int[] nums, int val) {
int fast = 0;
int slow = 0;
for(;fast < nums.length; fast++){
if(nums[fast] != val){
int temp = nums[slow];
nums[slow++] = nums[fast];
nums[fast] = temp;
}
return slow;
}
}
② [改进] 快指针筛选，慢指针只需按序填值即可
public int removeElement(int[] nums, int val) {
int fast = 0;
int slow = 0;
for(;fast < nums.length; fast++)
if(nums[fast] != val)
nums[slow++] = nums[fast];
return slow;
}
③ [改进] 减小数组减少遍历次数，末尾值替换该值
public int removeElement(int[] nums, int val) {
int i = 0;
int n = nums.length;
while(i < n)
if(nums[i] == val)
nums[i] = nums[--n];
else i++;
return n;
}
删除重复项Ⅰ
LeetCode26
① [线性表] 线性表删除思想需要移动大量尾部元素
public int removeDuplicates(int[] nums) {
int tail = nums.length;
int i = 1;
while (i < tail) {
if (nums[i - 1] == nums[i]) {
for (int j = i; j < tail - 1; j++) {
nums[j] = nums[j + 1];
}
tail--;
} else {
i++;
}
}
return tail;
}
② [双指针] 快指针对比筛选，慢指针依次覆盖
public int removeDuplicates(int[] nums) {
int slow = 0;
int fast = 1;
for(; fast < nums.length; fast++)
if(nums[fast] != nums[slow])
nums[++slow] = nums[fast];
return ++slow;
}
③ [改进] 取消开始位置不同值的原地复制
public int removeDuplicates(int[] nums) {
int slow = 0;
int fast = 1;
for(; fast < nums.length; fast++)
if(nums[fast] != nums[slow])
if(fast != slow)
nums[++slow] = nums[fast];
return ++slow;
}
删除重复项Ⅱ
LeetCode80
① [双指针] 快指针筛选与慢指针元素对比，慢指针依次填值，直到同一元素计数到2停止更新
public int removeDuplicates(int[] nums) {
int slow = 0;
int fast = 1;
int count = 1;
for (; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
count = 1;
} else {
if (count != 2) {
nums[++slow] = nums[fast];
count++;
}
}
}
return ++slow;
}
② [改进] 慢指针记录最后一个写入元素，快指针记录待插入慢指针之后元素。快指针与慢指针前一值相同，说明待插元素与前两个元素均相同不需插入，快指针向前遍历寻找新值即可。若不同，则说明待插值要么是第二个值，要么是新值，插在慢指针之后并更新慢指针。每个值最多可出现两次，则前两个必在结果集中，从第三个开始遍历即可。
public int removeDuplicates(int[] nums) {
int slow = 1;
int fast = 2;
for(; fast < nums.length; fast++)
if(nums[slow - 1] != nums[fast])
nums[++slow] = nums[fast];
return ++slow;
}
③ [改进] 若当前数大于前二位置数，说明是出现新值或第二个同样值，慢指针依次填值
public int removeDuplicates(int[] nums) {
if(nums.length <= 2) return nums.length;
for (int i = 2; i < nums.length; i++)
if (nums[i] != nums[i - 2])
nums[i++] = n;
return i;
}
④ [推广] 删除重复项，每个元素最多出现N次
public int removeDuplicates(int[] nums) {
int i = 0;
for (int n : nums)
if (i < N || N > nums[i - N])
nums[i++] = n;
return i;
}
颜色分类
LeetCode80
① [双指针/基数排序] 快指针遍历两次数组，每轮快指针从慢指针出发递增并筛选该值，交换该值到慢指针位置填入
public static void sortColors(int[] nums) {
int cur = 0;
int slow = 0;
for (; cur <= 1; cur++) {
for (int fast = slow; fast < nums.length; fast++) {
if (cur == nums[fast]) {
int temp = nums[slow];
nums[slow++] = nums[fast];
nums[fast] = temp;
}
}
}
}
② [改进] 三路快速排序。一次向前遍历，遇0交换到最左，遇2交换到最右。相当于一个快指针遍历，两个慢指针分别从两端向中间依次填入最小值和最大值
public static void sortColors(int[] nums) {
int i0 = 0;
int i1 = 0;
int i2 = nums.length - 1;
int tmp;
while (i1 <= i2) {
if (nums[i1] == 0) {
tmp = nums[i0];
nums[i0++] = nums[i1];
nums[i1++] = tmp;
}
else if (nums[i1] == 2) {
tmp = nums[i2];
nums[i2--] = nums[i1];
nums[i1++] = tmp;
}
else i1++;
}
}
寻找数组的中心索引
注意下标0处在右侧加和为0时也为中心索引，length - 1同理
① [暴力] 递增索引，每次验证左右部分和
public int pivotIndex(int[] nums) {
for(int i = 0; i < nums.length; i++) {
int left = 0;
int right = 0;
for(int j = 0; j < i; j++)
left += nums[j];
for(int k = nums.length - 1; k > i; k--)
right += nums[k];
if(left == right) return i;
}
return -1;
}
② [改进] 减少右侧和计算，右侧和 = 总和 – 左侧和 – 当前索引值。同理有 2 * 左侧和 = 总和 – 当前索引值
public int pivotIndex(int[] nums) {
int sum = 0;
int lef = 0;
for(int num: nums) sum += num;
for(int i = 0; i < nums.length; i++) {
if(lef == sum - lef - nums[i]) return i;
lef += nums[i];
}
return -1;
}
至少是其他数字两倍的最大数
LeetCode747
① [两次遍历] 一次找最大值，第二次验证条件
public static int dominantIndex(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; ++i)
if (nums[i] > nums[max])
max = i;
for (int i = 0; i < nums.length; ++i)
if (max != i && nums[max] <= 2 * nums[i])
return -1;
return maxIndex;
}
② [一次遍历] 一次遍历筛选最大值和次大值
public static int dominantIndex(int[] nums) {
if (nums.length < 1) return -1;
if (nums.length == 1) return 0;
int max = 0;
int smax = Integer.MIN_VALUE;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[max]) {
smax = nums[max];
max = i;
}
else if (nums[i] > smax && nums[max] != nums[i])
smax = nums[i];
}
return nums[max] >= smax * 2 ? max : -1;
}
加一
public int[] plusOne(int[] digits) {
for(int i = digits.length - 1; i >= 0; i--) {
if(digits[i] == 9) digits[i] = 0;
else{
digits[i]++;
return digits;
}
}
int arr = new int[digits.length + 1];
arr[0] = 1;
return arr;
}
对角线遍历
LeetCode498
① [数字规律] 列出遍历顺序下标寻找规律。仅适用于方阵，M×N矩阵报错
public static int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null) return new int[0];
if (matrix.length == 0) return new int[0];
if (matrix[0].length == 0) return new int[0];
int count = 0, n = matrix.length;
int[] nums = new int[n * matrix[0].length];
for (int i = 0; i < 2 * n - 1; i++) {
if (i < n)
if (i % 2 == 1)
for (int j = 0; j <= i; j++)
nums[count++] = matrix[j][i - j];
else
for (int j = i; j >= 0; j--)
nums[count++] = matrix[j][i - j];
else
if (i % 2 == 1)
for (int j = i - n + 1; j <= n - 1; j++)
nums[count++] = matrix[j][i - j];
else
for (int j = n - 1; j >= i - n + 1; j--)
nums[count++] = matrix[j][i - j];
}
return nums;
}
② [移动下标] 依次移动下标，坐标和为遍历层数，层数为偶数向右上移动，奇数左下移动，每到层末边界改变移动方向。
主对角线到达层末元素后改变方向与次对角线改变方向不同
须首先判断是否主对角线，再判断是否次对角线层末元素
颠倒则超出数组边界
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null) return new int[0];
if (matrix.length == 0) return new int[0];
if (matrix[0].length == 0) return new int[0];
int r = 0, c = 0;
int row = matrix.length;
int col = matrix[0].length;
int[] arr = new int[row * col];
for (int i = 0; i < arr.length; i++) {
arr[i] = matrix[r][c];
if ((r + c) % 2 == 0) {
if (c == col - 1) r++;
else if (r == 0) c++;
else { r--; c++; }
}
else {
if (r == row - 1) c++;
else if (c == 0) r++;
else { r++; c--; }
}
}
return arr;
}
旋转数组
LeetCode189
① [暴力求解] 每次批量移动一位移动k次
依次移动，单独处理末位和头部
public void rotate(int[] nums, int k) {
int l = nums.length;
if (l > 0) {
for (int i = 0; i < k; i++) {
int t = nums[l - 1];
for (int j = l - 1; j > 0; j--)
nums[j] = nums[j - 1];
nums[0] = t;
}
}
保存被覆盖值，供下次循环赋值
public void rotate(int[] nums, int k) {
int p = nums[l - 1];
for (int j = 0; j < l; j++) {
int t = nums[j];
nums[j] = p;
p = t;
}
}
② [额外内存] 开辟另外一个数组，直接放入正确位置
public void rotate(int[] nums, int k) {
if (nums.length > 1) {
int[] arr = new int[nums.length];
for (int i = 0; i < nums.length; i++)
arr[(i + k) % nums.length] = nums[i];
for (int i = 0; i < nums.length; i++)
nums[i] = arr[i];
}
}
③ [★] 待续
长度最小的子数组
LeetCode209
① [暴力求解] 枚举下标所有情况
public static int minSubArrayLen(int s, int[] nums) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
int sum = 0;
for (int k = i; k <= j; k++)
sum += nums[k];
if (sum >= s) {
int val = j - i + 1;
if (min > val) min = val;
}
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
② [优化] 待续
③ [滑动窗口] 慢指针原地等待，快指针向前遍历加和，直到和满足条件。慢指针前移后重复上述操作，记录最小序列长度。快指针到达末尾停止。
public int minSubArrayLen(int s, int[] nums) {
int l = 0, r = 0;
int sum = 0, tmp = 0;
int min = Integer.MAX_VALUE;
while (l < nums.length) {
if (sum < s && r < nums.length)
sum += nums[r++];
else sum -= nums[l++];
tmp = r - l;
if (min > tmp && sum >= s)
min = tmp;
}
}
详细说明
输入 [2, 3, 1, 2, 4, 3]
window l r sum min tmp
2 0 1 2 MAX 1
23 0 2 5 MAX 2
231 0 3 6 MAX 3
2312 0 4 8 4 4
312 1 4 6 4 3
3124 1 5 10 4 4
124 2 5 7 3 3
24 3 5 6 3 2
243 3 6 9 3 3
43 4 6 7 2 2
3 5 6 3 2 1
6 6 0 2 0
④ [优化] 仅在缩小窗口（慢指针前移）时计算比较上次长度
public int minSubArrayLen(int s, int[] nums) {
int l = 0, r = 0;
int sum = 0, tmp = 0;
int min = Integer.MAX_VALUE;
while (l < nums.length) {
if (sum < s && r < nums.length)
sum += nums[r++];
else {
if (sum < s) break;
tmp = r - l;
if (min > tmp)
min = tmp;
sum -= nums[l++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
详细说明
输入 [2, 3, 1, 2, 4, 3]
window l r sum min tmp 2 0 1 2 MAX 0 23 0 2 5 MAX 0 231 0 3 6 MAX 0 2312 0 4 8 MAX 0 312 1 4 6 4 4 3124 1 5 10 4 4 124 2 5 7 4 4 24 3 5 6 3 3 243 3 6 9 3 3 43 4 6 7 3 3 3 5 6 3 2 2
最大子序和
LeetCode53
不断更新最大和，其中负和对最大和无贡献，清零重计
public int maxSubArray(int[] nums) {
int cur = 0;
int sum = 0;
int max = nums[0];
while (cur < nums.length) {
sum += nums[cur];
max = sum > max ? sum : max;
sum = sum > 0 ? sum : 0;
cur++;
}
return max;
}