[LeetCode 笔记] 15. 3Sum

前言

　　这题是一个运用指标的算法，而且是用三个指标来追蹤，运用指标依序扫瞄出题目所要的元素并加起来，使用到了 for、while 两个迴圈，时间複杂度估达 O(n²)，这里有 JAVA 和 Python 的写法。

题目

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

给定一个整数阵列 nums，回传所有的三元组，其中 i != j, i != k, j != k，且三元组全部加起来等于 0。
注意 这个解决方案必须不含重複的三元组。

题目连结：https://leetcode.com/problems/3sum/

题目限制

3 <= nums.length <= 3000
105 <= nums[i] <= 105

範例

Input: nums = [-1,0,1,2,-1,-4]Output: [[-1,-1,2],[-1,0,1]]Explanation: 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.The distinct triplets are [-1,0,1] and [-1,-1,2].Notice that the order of the output and the order of the triplets does not matter.

Input: nums = [0,1,1]Output: []Explanation: The only possible triplet does not sum up to 0.

Input: nums = [0,0,0]Output: [[0,0,0]]Explanation: The only possible triplet sums up to 0.

思路&笔记

直观的作法是设定三个指标来扫描，第一个指标先不动，另外两个指标依序扫描元素，扫描后把全部的元素加起来，判断里面的合有没有等于 0 的，有的话就加入在要输出的阵列里，资料结构想到的是把阵列里的元素个别放进集合里，再将每一组串列集合放进 HashSet 大集合里，HashSet 好处是可过滤掉重複的组合。

将 Array 从小到大排序找出三个数的指标分别表示为 i、j、k使用迴圈遍历，并将 i 做为 nums 的起始点 (指标一)j 则为 i + 1 为起始 (指标二)k 则为 nums.Length - 1 为起始点 (指标三)首先以 i 为準，从 j 开始扫描到 k 算一轮并判断三个指标指向的元素 nums[i] + nums[j] + nums[k] 加起来的合是否为 0 ，是的话会把此组合加进串列集合内之后让 j 前进一格，K 后退一格，来排除重複的组合找到下一个组合由于元素从小排到大，当 sum < target 的话，表示说我们的 j 要继续往右扫描到一个更大的元素，加起来的合再做判断那元素从小排到大，当 sum > target 的话，表示说我们的 k 要继续往左扫描到一个更小的元素，加起来的合再做判断

[备注] 使用 HashSet 是为了确保集合里的资料不重複

简易示意图

| -4  | -1  | -1  |  0  |  1  |  2  ||-----|-----|-----|-----|-----|-----||  i  |  j  |     |     |     |  k  |sum = (-4) + (-1) + 2 = -3sum < 0，j++

| -4  | -1  | -1  |  0  |  1  |  2  ||-----|-----|-----|-----|-----|-----||  i  |     |  j  |     |     |  k  |sum = (-4) + (-1) + 2 = -3sum < 0，j++

| -4  | -1  | -1  |  0  |  1  |  2  ||-----|-----|-----|-----|-----|-----||  i  |     |     |  j  |     |  k  |sum = (-4) + 0 + 2 = -2sum < 0，j++

| -4  | -1  | -1  |  0  |  1  |  2  ||-----|-----|-----|-----|-----|-----||  i  |     |     |     |  j  |  k  |sum = (-4) + 1 + 2 = -1sum < 0，j++j == k，回到最新一轮，i++

| -4  | -1  | -1  |  0  |  1  |  2  ||-----|-----|-----|-----|-----|-----||     |  i  |  j  |     |     |  k  |sum = (-1) + (-1) + 2 = 0，加进集合j++k--

| -4  | -1  | -1  |  0  |  1  |  2  ||-----|-----|-----|-----|-----|-----||     |  i  |     |  j  |  k  |     |sum = (-1) + 0 + 1 = 0，加进集合j++k--j > k，回到最新一轮，i++

| -4  | -1  | -1  |  0  |  1  |  2  ||-----|-----|-----|-----|-----|-----||     |     |  i  |  j  |     |  k  |i 与上次相同，回到最新一轮，i++

| -4  | -1  | -1  |  0  |  1  |  2  ||-----|-----|-----|-----|-----|-----||     |     |     |  i  |  j  |  k  |sum = 0 + 1 + 2 = 3

JAVA 实现

class Solution {    public List<List<Integer>> threeSum(int[] nums) {        int target = 0; // 目标整数        Arrays.sort(nums); // 从小到大排序 (原Array)        Set<List<Integer>> s = new HashSet<>(); // 存元素        List<List<Integer>> output = new ArrayList<>(); // 输出用        for (int i = 0; i < nums.length; i++){            int j = i + 1; // 指标二            int k = nums.length - 1; // 指标三            while (j < k) {                int sum = nums[i] + nums[j] + nums[k]; // 指标全加起来                if (sum == target) {// 将阵列元素转成集合再加到大集合内                    // 类似这样的资料结构 [[1, 2, 3], [2, 3, 4]]                    s.add(Arrays.asList(nums[i], nums[j], nums[k]));                     // 缩小範围                    j++;                     k--;                } else if (sum < target) {                    j++; // 找更大的元素                } else {                    k--; // 找更小的元素                }            }        }        output.addAll(s); // 集合加到阵列里        return output;    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def threeSum(self, nums: List[int]) -> List[List[int]]:                target = 0 # 目标整数        nums.sort() # 从小到大排序 (原Array)        s = set() # 存元素的集合        output = [] # 输出用的阵列                for i in range(len(nums)):            j = i + 1 # 指标二            k = len(nums) - 1 # 指标三            while j < k:                total = nums[i] + nums[j] + nums[k] # 指标全加起来                if total == target:                    s.add((nums[i], nums[j], nums[k])) # 将阵列元素加到集合内                    j = j+1 # 缩小範围                    k = k-1                elif total < target:                    j = j+1 # 找更大的元素                else:                    k = k-1 # 找更小的元素                output.extend(list(s)) # 添加进阵列        return output

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/06/16/LeetCode-15-3Sum-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论