数组与双指针

数组是面试中最基础也最高频的数据结构，双指针技巧则是解决数组问题的核心武器。本模块涵盖两数之和、三数之和、接雨水等经典题目，掌握快慢指针、左右指针、滑动窗口等核心思想，能帮你高效解决大多数数组类问题。

---

Q1: 两数之和 「🟢 初级」

题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个整数，返回它们的数组下标。你可以假设每种输入只会对应一个答案，且同一个元素不能使用两次。

考察点：哈希表的应用、数组遍历、空间换时间思想。

解题思路：

• 方法1：暴力解法，两层循环遍历所有数对（时间O(n²)，空间O(1)）
• 方法2：哈希表，一次遍历，用哈希表存储已访问的数字及其索引（时间O(n)，空间O(n)）- 最优解

代码实现：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[]{-1, -1};
}

复杂度分析：时间复杂度 O(n)，仅遍历一次数组；空间复杂度 O(n)，哈希表最多存储 n 个元素。

变体扩展：

• 变体1：三数之和
• 变体2：四数之和
• 变体3：两数之和II（有序数组，双指针解法）
• 变体4：两数之和III（数据结构设计）

---

Q2: 三数之和 「🟡 中级」

题目描述：给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

考察点：排序 + 双指针、去重技巧、三指针思想。

解题思路：

• 方法1：暴力三层循环（时间O(n³)，空间O(1)）- 超时
• 方法2：排序 + 双指针，固定一个数，剩下两数用双指针查找（时间O(n²)，空间O(1)）- 最优解

代码实现：

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++; // 去重
                while (left < right && nums[right] == nums[right - 1]) right--; // 去重
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return res;
}

复杂度分析：时间复杂度 O(n²)，排序 O(nlogn) + 双层遍历 O(n²)；空间复杂度 O(1)（忽略排序的栈空间）。

变体扩展：

• 变体1：最接近的三数之和
• 变体2：四数之和
• 变体3：较小的三数之和

---

Q3: 移除元素 「🟢 初级」

题目描述：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

考察点：快慢指针、原地修改数组。

解题思路：

• 方法1：快慢指针，慢指针指向新数组末尾，快指针遍历（时间O(n)，空间O(1)）- 最优解
• 方法2：双指针优化（当要删除的元素很少时），从两端向中间遍历

代码实现：

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

复杂度分析：时间复杂度 O(n)，遍历一次数组；空间复杂度 O(1)，原地修改。

变体扩展：

• 变体1：删除有序数组中的重复项
• 变体2：删除有序数组中的重复项II（最多保留2个）
• 变体3：移动零

---

Q4: 删除有序数组中的重复项 「🟢 初级」

题目描述：给你一个升序排列的数组 nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。

考察点：快慢指针、有序数组特性、原地修改。

解题思路：

• 方法1：快慢指针，慢指针指向不重复部分的末尾，快指针遍历（时间O(n)，空间O(1)）- 最优解

代码实现：

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

复杂度分析：时间复杂度 O(n)，遍历一次数组；空间复杂度 O(1)，原地修改。

变体扩展：

• 变体1：删除有序数组中的重复项II（每个元素最多出现2次）
• 变体2：移除元素
• 变体3：有序链表删除重复节点

---

Q5: 合并两个有序数组 「🟢 初级」

题目描述：给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

考察点：双指针从后向前遍历、原地合并。

解题思路：

• 方法1：先合并再排序（时间O((m+n)log(m+n))，空间O(1)）
• 方法2：双指针从前往后，需要额外数组（时间O(m+n)，空间O(m)）
• 方法3：双指针从后往前，原地合并（时间O(m+n)，空间O(1)）- 最优解

代码实现：

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

复杂度分析：时间复杂度 O(m+n)，最多遍历 m+n 个元素；空间复杂度 O(1)，原地修改。

变体扩展：

• 变体1：合并两个有序链表
• 变体2：合并k个有序链表
• 变体3：有序数组的平方

---

Q6: 接雨水 「🔴 高级」

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

考察点：双指针、单调栈、动态规划、空间优化。

解题思路：

• 方法1：暴力解法，每个位置找左右最大高度（时间O(n²)，空间O(1)）
• 方法2：动态规划，预处理左右最大高度数组（时间O(n)，空间O(n)）
• 方法3：双指针，左右指针向中间移动（时间O(n)，空间O(1)）- 最优解
• 方法4：单调栈

代码实现：

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int res = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                res += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                res += rightMax - height[right];
            }
            right--;
        }
    }
    return res;
}

复杂度分析：时间复杂度 O(n)，左右指针各遍历一次；空间复杂度 O(1)，仅使用常数额外空间。

变体扩展：

• 变体1：盛最多水的容器
• 变体2：柱状图中最大的矩形
• 变体3：接雨水II（二维）

---

Q7: 盛最多水的容器 「🟡 中级」

题目描述：给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

考察点：双指针、贪心思想。

解题思路：

• 方法1：暴力解法，枚举所有数对（时间O(n²)，空间O(1)）
• 方法2：双指针，左右指针向中间移动，每次移动较短的一边（时间O(n)，空间O(1)）- 最优解

代码实现：

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

复杂度分析：时间复杂度 O(n)，左右指针各遍历一次；空间复杂度 O(1)，常数额外空间。

变体扩展：

• 变体1：接雨水
• 变体2：装最多水的容器III

---

Q8: 下一个排列 「🟡 中级」

题目描述：整数数组的一个排列就是将其所有成员以序列或线性顺序排列。给你一个整数数组 nums，找出 nums 的下一个排列。必须原地修改，只允许使用额外常数空间。

考察点：双指针、排列规律、原地反转。

解题思路：

• 方法：从后向前找第一个下降的位置i，再从后向前找第一个比nums[i]大的位置j，交换i和j，然后反转i之后的部分（时间O(n)，空间O(1)）- 最优解

代码实现：

public void nextPermutation(int[] nums) {
    int i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = nums.length - 1;
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        swap(nums, i, j);
    }
    reverse(nums, i + 1, nums.length - 1);
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        swap(nums, start, end);
        start++;
        end--;
    }
}

复杂度分析：时间复杂度 O(n)，最多遍历三次数组；空间复杂度 O(1)，原地修改。

变体扩展：

• 变体1：上一个排列
• 变体2：全排列
• 变体3：第k个排列

---

Q9: 旋转数组 「🟡 中级」

题目描述：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。你必须使用空间复杂度为 O(1) 的原地算法解决这个问题。

考察点：三次翻转法、环状替换、原地旋转。

解题思路：

• 方法1：使用额外数组（时间O(n)，空间O(n)）
• 方法2：三次翻转法，先翻转整体，再翻转前k个，再翻转后n-k个（时间O(n)，空间O(1)）- 最优解
• 方法3：环状替换

代码实现：

public void rotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

复杂度分析：时间复杂度 O(n)，每个元素被翻转两次；空间复杂度 O(1)，原地修改。

变体扩展：

• 变体1：旋转链表
• 变体2：旋转图像
• 变体3：搜索旋转排序数组

---

Q10: 除自身以外数组的乘积 「🟡 中级」

题目描述：给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。

考察点：前缀积 + 后缀积、空间优化、双指针思想。

解题思路：

• 方法1：左右乘积数组，分别计算前缀积和后缀积（时间O(n)，空间O(n)）
• 方法2：空间优化，用输出数组存储前缀积，再从右向左乘后缀积（时间O(n)，空间O(1)，输出数组不计入）- 最优解

代码实现：

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    // 前缀积
    res[0] = 1;
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }
    // 后缀积
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] *= right;
        right *= nums[i];
    }
    return res;
}

复杂度分析：时间复杂度 O(n)，两次遍历数组；空间复杂度 O(1)（输出数组不计入空间复杂度）。

变体扩展：

• 变体1：乘积最大子数组
• 变体2：和为K的子数组
• 变体3：除自身以外数组的和