(双指针 ) 15. 三数之和 ——【Leetcode每日一题】

这篇具有很好参考价值的文章主要介绍了(双指针 ) 15. 三数之和 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

❓15. 三数之和

难度:中等

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != 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 < = n u m s . l e n g t h < = 3000 3 <= nums.length <= 3000 3<=nums.length<=3000
  • − 1 0 5 < = n u m s [ i ] < = 1 0 5 -10^5 <= nums[i] <= 10^5 105<=nums[i]<=105

💡思路:双指针

其实这道题目使用哈希法并不十分合适,因为在去重的操作中有很多细节需要注意,在面试中很难直接写出没有 bug 的代码。
而且使用哈希法 在使用两层 for 循环的时候,能做的剪枝操作很有限,虽然时间复杂度是 O ( n 2 ) O(n^2) O(n2),也是可以在leetcode上通过,但是程序的执行时间依然比较长 。

这里使用双指针法

(双指针 ) 15. 三数之和 ——【Leetcode每日一题】
拿这个 nums 数组来举例,首先将数组排序,然后有一层 for 循环,i 从下标 0 的地方开始,同时定一个下标 left 定义在 i +1的位置上,定义下标 right 在数组结尾的位置上。
依然还是在数组中找到 a b c 使得 a + b +c = 0,我们这里相当于 a = nums[i]b = nums[left]c = nums[right]:

  • 如果 nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了,因为数组是排序后了,所以 right 下标就应该向左移动,这样才能让三数之和小一些
  • 如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了,left 就向右移动,才能让三数之和大一些,直到 leftright 相遇为止。

答案中不可以包含重复的三元组,所以要考虑去重

  • 由于和为 0 ,所以只有三个数都为 0 时,才可能三个数同时相等,如果有这种情况,则加入结果,退出循环,因为后面的任意三个数都大于等于0;
  • 每次循环三个数中的第一个数 num[i] 都不同,避免重复
  • 如果后两个相等,则只加这一种情况,退出循环;

🍁代码:(Java、C++)

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length - 1;
        for(int i = 0; i < n - 1; i++){//遍历到数组倒数第三个数即可
            if(nums[i] == 0){
                if(nums[i + 2] == 0){
                    ans.add(Arrays.asList(0, 0, 0));
                }
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]) continue; //去重,每次循环第一个数都不同

            int left = i + 1, right = n;
            
            while(left < right){
                if(nums[left] + nums[right] < -nums[i]) left++;
                else if(nums[left] + nums[right] > -nums[i]) right--;
                else{
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    if(nums[left] == nums[right]) break;//去重,后两个相同则结束循环
                    while(left < right && nums[left + 1] == nums[left]) left++; //找到下一个比left大的数
                    left++;
                    while(left < right && nums[right - 1] == nums[right]) right--; //找到下一个比right小的数
                    right--;
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int n = nums.size() - 1;
        for(int i = 0; i < n - 1; i++){
            if(nums[i] == 0) {
                if(nums[i + 2] == 0){
                    ans.push_back({0,0,0});
                }
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]) continue;//去重,每次循环第一个数都不同

            int left = i + 1, right = n;
            
            while(left < right){
                if(nums[left] + nums[right] < -nums[i]) left++;
                else if(nums[left] + nums[right] > -nums[i]) right--;
                else{
                    ans.push_back({nums[i], nums[left], nums[right]});
                    if(nums[left] == nums[right]) break;//去重,后两个相同则结束循环
                    while(left < right && nums[left + 1] == nums[left]) left++;//找到下一个比left大的数
                    left++;
                    while(left < right && nums[right - 1] == nums[right]) right--;//找到下一个比right小的数
                    right--;
                }
            }
        }
        return ans;
    }
};
🚀 运行结果:

(双指针 ) 15. 三数之和 ——【Leetcode每日一题】

🕔 复杂度分析:
  • 时间复杂度 O ( n 2 ) O(n^2) O(n2),其中 n 为数组 nums 的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1),忽略存储答案的空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-488795.html

注: 如有不足,欢迎指正!

到了这里,关于(双指针 ) 15. 三数之和 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023/07/11_leetcode每日一题_16. 最接近的三数之和

    给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 和三数之和那道题一样,排序加双指针

    2024年02月15日
    浏览(61)
  • [双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和

    [双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和 查找总价格为目标值的两个商品 LCR 179. 查找总价格为目标值的两个商品 题目分析 (1) 数组内数字是升序 (2) 目标值为target (3) 找两数之和为target 解题思路 找两个数字的和与目标值相等,我们可以想到

    2024年02月05日
    浏览(44)
  • 2023-07-15 LeetCode每日一题(四数之和)

    点击跳转到题目位置 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且 不重复 的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复): 0 = a, b, c, d n a、b、c 和 d 互不相同 nums[a] + nums[b]

    2024年02月16日
    浏览(45)
  • (双指针 ) 18. 四数之和 ——【Leetcode每日一题】

    难度:中等 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且 不重复 的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复): 0 = a, b, c, d n a 、 b 、 c 和 d 互不相同 nums[a] + nums[b] + nums[c

    2024年02月07日
    浏览(53)
  • Leetcode每日一题:18. 四数之和(2023.7.15 C++)

    目录 18. 四数之和 题目描述: 实现代码与解析: 双指针 原理思路:         给你一个由  n  个整数组成的数组  nums  ,和一个目标值  target  。请你找出并返回满足下述全部条件且 不重复 的四元组  [nums[a], nums[b], nums[c], nums[d]]  (若两个四元组元素一一对应,则认为

    2024年02月16日
    浏览(57)
  • LeetCode15.三数之和

    15.三数之和 一、题目 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j 、 i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三元组。 **注意:**答案中不可以包含重复的三元组。 示例 1: 示例 2: 示例 3: 提

    2024年02月13日
    浏览(55)
  • LeetCode - 15 三数之和

    目录 题目来源 题目描述 示例 提示 题目解析 算法源码 题目来源 15. 三数之和 - 力扣(LeetCode) 题目描述 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三

    2024年02月09日
    浏览(38)
  • LeetCode 15. 三数之和

    题目链接 15. 三数之和 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j 、 i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三元组。 **注意:**答案中不可以包含重复的三元组。 示例 1: 示例 2: 示例 3:

    2024年02月08日
    浏览(34)
  • 【leetcode】15. 三数之和(medium)

    给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。 这题真的好难,试了好多方法,最后参考了代码随想录的

    2024年02月13日
    浏览(50)
  • leetcode15. 三数之和(java)

    给你一个整数数组 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,

    2024年02月10日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包