首页 > 其他分享 >【双指针】LeetCode 18. 四数之和

【双指针】LeetCode 18. 四数之和

时间:2023-01-30 10:14:38浏览次数:61  
标签:四数 nums int 18 long while && LeetCode

题目链接

18. 四数之和

思路

【双指针】LeetCode 15. 三数之和 思路相似,但是要注意测试用例可能溢出,需要转换为 long

代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();

        for(int a = 0; a < nums.length - 3; a++){
            if(a > 0 && nums[a] == nums[a - 1]){
                continue;
            }
            for(int b = a + 1; b < nums.length - 2; b++){
                if(b > a + 1 && nums[b] == nums[b - 1]){
                    continue;
                }

                int c = b + 1;
                int d = nums.length - 1;
                while(c < d){
                    long sum = (long)nums[a] + (long)nums[b] + (long)nums[c] + (long)nums[d];
                    if(sum == target){
                        result.add(Arrays.asList(nums[a], nums[b], nums[c], nums[d]));
                        while(c < d && nums[c + 1] == nums[c]){
                            c++;
                        }
                        while(c < d && nums[d - 1] == nums[d]){
                            d--;
                        }
                        c++;
                        d--;
                    }else if(sum > target){
                        d--;
                    }else{
                        c++;
                    }
                }

            }
        }

        return result;
    }
}

标签:四数,nums,int,18,long,while,&&,LeetCode
From: https://www.cnblogs.com/shixuanliu/p/17074553.html

相关文章

  • LeetCode:1669. 合并两个链表
    /***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListN......
  • 2018-8-12 板爷第二课
    板爷课程地址:第一集? http://v.youku.com/v_show/id_XOTM5NTIxNzEy.html?第二集? http://v.youku.com/v_show/id_XOTYwNzk3Njc2.html第三集? http://v.youku.com/v_s......
  • 2018-8-12 板爷第一课
     https://v.youku.com/v_show/id_XMTI2NDQ5NDk4NA==.html板爷推荐:心得心法?搜不到这本书提问:收费软件是否有用?板爷:我自己用通达信,东方财富通。但是收费软件,首先看收费软......
  • leetcode简单(矩阵):[566, 766, 832, 867, 999, 1030, 1261, 1275, 1337, 1351]
    目录566.重塑矩阵766.托普利茨矩阵832.翻转图像867.转置矩阵999.可以被一步捕获的棋子数1030.距离顺序排列矩阵单元格1260.二维网格迁移1275.找出井字棋的获胜者13......
  • LeetCode-21.合并两个有序链表
    21.合并两个有序链表(MergeTwoSortedLists)将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例1:输入:l1=[1,2,4......
  • ERROR 1862 (HY000): Your password has expired. To log in you must change it usin
    navcat登录本地失败 https://blog.csdn.net/fenniang16/article/details/81216602?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-......
  • LeetCode_周赛_330
    6337.统计桌面上的不同数字代码后面出现的数字都是小于n的。n=1时,答案是1。n>1时:第一天,n%(n-1)==1,n-1会被加入第二天,(n-1)%(n-2)==1,n-......
  • leetcode 15. 三数之和
    想到了先排序然后再用双指针,可是没有想过往O(n^2)的时间复杂度上怼。哈哈哈。正确解法如下:classSolution{publicList<List<Integer>>threeSum(int[]nums){......
  • Adobe Flash Player 10.3.181.22 Final
    InternetExplorer:​​​http://fpdownload.macromedia.com/get/flashplayer/current/licensing/win/install_flash_player_10_active_x.exe​​Firefox,Safari,Opera:​......
  • 【双指针】LeetCode 16. 最接近的三数之和
    题目链接16.最接近的三数之和思路借鉴【双指针】LeetCode15.三数之和的思路,只不过把0换成target代码classSolution{publicintthreeSumClosest(int[]n......