LeetCode - 缺失的第一个正数 / 三数之和

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

• 1 <= nums.length <= 105

• -231 <= nums[i] <= 231 - 1

解题思路

原地哈希

原地归位（for + while 循环）

遍历数组，把每个有效正整数放到它「应该在」的位置上（数字 x 应该放在索引 x-1 处）：

• 循环条件拆解（while 里的四个条件同时满足才会交换）：

  1. nums[i] > 0：只处理正整数（负数 / 0 不可能是「缺失的最小正整数」）；

  2. nums[i] != i + 1：当前数字不在正确位置（如果已经在正确位置，无需交换）；

  3. nums[i] - 1 < nums.length：确保数字对应的目标索引不越界（比如数组长度为 3，数字 5 的目标索引是 4，超出数组范围，无需处理）；

  4. nums[i] != nums[nums[i] - 1]：避免死循环（比如数组 [1,1]，如果没有这个条件，会一直交换两个 1）。

• 交换逻辑：

  把 nums[i] 交换到它的目标索引 nums[i]-1 处，确保数字 x 最终出现在 nums[x-1] 的位置。

查找缺失值

遍历归位后的数组，第一个满足 nums[i] != i+1 的位置 i，对应的 i+1 就是缺失的最小正整数；如果所有位置都匹配，说明数组包含 1~n 所有数，返回 n+1。

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] != i + 1 && nums[i] - 1 < nums.length && nums[i] != nums[nums[i] - 1]) {
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

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

三数之和

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

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

解题思路

核心思路是排序 + 双指针，把三元组问题转化为「固定一个数 + 两数之和」的问题，同时通过排序天然解决重复问题：

1. 排序数组：先对数组排序，一方面能让双指针移动有规律，另一方面能快速跳过重复元素；

2. 固定第一个数：遍历数组，每次固定 nums[i] 作为三元组的第一个数，目标转化为在 i 右侧找两个数，使其和为 -nums[i]；

3. 双指针找另外两个数：用左指针 left = i+1、右指针 right = nums.length-1，根据两数之和与 -nums[i] 的大小关系移动指针；

4. 去重处理：

   • 固定的第一个数 nums[i] 若和前一个数相同，直接跳过（避免重复三元组）；

   • 找到符合条件的两个数后，跳过左侧 / 右侧的重复值（避免重复三元组）。

class Solution {
	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		Arrays.sort(nums);
		for (int i = 0; i < nums.length - 2; i++) {

			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}

			int pre = nums[i];
			int start = i + 1;
			int end = nums.length - 1;

			while (start < end) {
				int total = nums[start] + nums[end] + pre;
				if (total == 0) {
					result.add(Arrays.asList(pre, nums[start], nums[end]));

					while (start < end && nums[start] == nums[start + 1]) {
						start++;
					}
					while (start < end && nums[end] == nums[end - 1]) {
						end--;
					}
					start++;
					end--;
				} else if (total > 0) {
					end--;
				} else {
					start++;
				}
			}
		}
		return result;
	}
}