lc15. 三数之和-编程思维

 题目来源于力扣题库,题目链接:LC15. 三数之和

Q:给你一个整数数组 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 。

提示:

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

A:思路:题目给出的要求是从一个整数数组中不断找到三数之和为0的三元组,条件是这三个数所对应的索引均不相同,且结果集中不能存在重复的三元组。

  拿到该题,最容易想到的是用暴力解法,三个for循环开干。但是,通过对时间复杂度的一个分析,发现这样是行不通的,随后,曾经做过的两数之和的思路可能突然间给了自己一个思路,即用哈希表来做。事实上,利用哈希表是可以做出来的,但是过程有些过于复杂,尤其是对于去重问题,且时间复杂度也不低。

  最后,只能去求助于双指针,双指针的主要思路是先对数组进行排序,然后利用一层for循环去的固定一个数值nums[i](i∈[0, nums.length - 1]),随后构建两个指针left和right,初始化使得left = i + 1,right = nums.length - 1(left指向i的下一个数值,right指向nums的最后一个数值),在while(left < right)循环中,去使得left和right不断的靠近,即left++,right--。由于数组是经过排序的,所以是递增的,当遇到nums[i] + nums[left] + nums[right] > 0时,说明和太大了,那么我们就让right指针往前移动right--,使得和变小一点;同理如果遇到nums[i] + nums[left] + nums[right] < 0时,那么说明总和太小了,我们就让left指针往后移动left++,使得和变大一点。这样不断的去找到满足nums[i] + nums[left] + nums[right] == 0 的三个数值,且它们的下标是不重复的,但是还有一个问题就是,如何解决结果集中重复的三元组组合问题呢?

  这里便涉及到了关键的操作:去重,如何去重,举例来讲,例如有一数组: {-1, -1, -1, 2},我们可以发现,里面的一个组合{-1, -1, 2}是满足题意的,但是如果不进行去重操作,那么就会出现重复的三元组{-1, -1, 2}。解决该问题的一个关键思路是如果当前for循环中需要固定的数值num[i] == nums[i-1]时,就直接continue,跳过此轮for循环。为什么要这样?因为nums[i - 1]已经被我们用过了,且其后面对应的一些可以满足组合的数值也都用过了,均加入了结果集中了。那么如果现在我们还使用与nums[i-1]相同数值的nums[i],并且同样的往后找到满足的组合,那么必定会出现重复的三元组,简单来说就是又以同样的数值nums[i]去找了一遍满足题意的组合。

  故我们得知去重的第一个条件就是在for循环中,如果遇到i > 0 && nums[i] == nums[i - 1],则直接continue,开启下一轮for循环。但是现在似乎只完成了一次去重,还有二次去重,例如nums:{0, -1, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1},我们可以很容易的找到满足题意的三元组{0,-1,1},但是此时会出现往后的{0,-1,1}还是满足的,显然这是不符合题意的,虽然它们三个下标不同,但是三元组是重复的。其实这个问题其实很好解决,当我们发现nums[left] == nums[left + 1] 时,就让left指针不断的往后移动,即left++,跳过那些重复的数值;同理当我们发现nums[right] == nums[right - 1]时,就让right指针不断的往前移动,即right--即可,至此,二次去重问题便解决了。

  最后要说的是,每当找到一组满足题意的三元组加入到结果集后,且二次去重完成后,还要进行一次left++和right--,使得left和right指针指向下一个需要判断的三元组。

  以下是Java代码,仅供参考:

 

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        int n = nums.length;

        Arrays.sort(nums); // 排序

        for(int i = 0; i < n; i++){
            if(nums[i] > 0) return res; // 排序后的第一个数值如果已经大于0,则直接返回res

            if(i > 0 && nums[i] == nums[i - 1]) continue; // 一次去重

            int left = i + 1; // 对于每一次的i,更新left
            int right = n - 1; // 对于每一次的i,更新right

            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];

                if(sum < 0){ // 总和太小了,使left往后挪一挪
                    ++left;
                }else if(sum > 0){ // 总和太大了,使right往前挪一挪
                    --right;
                }else{
                    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; // 指向下一个待判断的数值
                }
            }
        }
        return res;
    }
}

 

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://www.cnblogs.com/fxy0715/p/17418493.html

lc19. 删除链表的倒数第 n 个结点-编程思维

删除链表的倒数第N个结点(中等) Q:给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。   示例: 示例一:输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例二:输入:head = [1], n = 1 输出:[] 实例三:输入:head = [1,2], n

lc2. 两数相加-编程思维

Q:给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储 一位数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。 示例:   示例1: 输入:l1 = [2,4,3], l2 = [5,6,4] 输出:

lc206. 反转链表-编程思维

Q:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。  示例: 示例1: 输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1] 示例2: 输入:head = [1,2] 输出:[2,1] 示例3: 输入:head = [] 输出:[] 提示: 链表中节点的数目范围是 [0

lc56. 合并区间-编程思维

题目来源于力扣题库,题目链接:LC56.合并区间 Q:以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。 示例1: 输入:intervals = [[