程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode][Java] 4Sum

[LeetCode][Java] 4Sum

編輯:C++入門知識

[LeetCode][Java] 4Sum


題目:

 

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • The solution set must not contain duplicate quadruplets.

     

        For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
    
        A solution set is:
        (-1,  0, 0, 1)
        (-2, -1, 1, 2)
        (-2,  0, 0, 2)

    題意:

    給定一個包含n個整數的數組S,在數組S中是否存在元素a,b,c和d,使得 a + b + c + d = target.找出數組S中所有這樣的組合。

    注意:

    1.這四個元素必須是升序排列(ie, a ≤ b ≤ c ≤ d)

    2.最終結果中不嫩包含重復的解。

     

        For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
    
        A solution set is:
        (-1,  0, 0, 1)
        (-2, -1, 1, 2)
        (-2,  0, 0, 2)

     

    算法分析:

    * 利用了題目《3Sum》的代碼 https://leetcode.com/problems/3sum/
    * 首先升序排列數組,然後從第一個元素開始依次遍歷《3Sum》算法,目標值為(target-nums[i]),遍歷的數組為該元素後面的數組
    * 這樣既滿足最終的arraylist中元素升序排列,也不會出現重復,因為每次以其為開始,進行遍歷的元素都是數組中的最小的元素

    AC代碼:

     

    public class Solution 
    {
        private static ArrayList> ret = new ArrayList>();
        
        public ArrayList> fourSum(int[] nums, int target) 
        {
            int newtarget=0;
        
            ArrayList> finalres = new ArrayList>();
            Arrays.sort(nums);
        	for (int i = 0; i < nums.length; i++) 
            {
        		 ArrayList> temlist= new ArrayList>();
        		if (i > 0 && nums[i] == nums[i-1]) continue;//避免結果重復,其後面和它相等的直接被跳過。
                newtarget=target-nums[i];
                int inputnums[]=new int[nums.length -i-1];
                for(int ii=0;ii> threeSum(int[] num,int newtarget,int firstnum) 
        {
            if (num == null || num.length < 3) return ret;
            
            Arrays.sort(num);
            
            int len = num.length;
            for (int i = 0; i < len-2; i++) 
            {
                if (i > 0 && num[i] == num[i-1]) continue;//避免結果重復,其後面和它相等的直接被跳過。
                find(num, i+1, len-1, num[i],newtarget, firstnum); //尋找兩個數與num[i]的和為0
            }
            
            return ret;
        }
        
        public static void find(int[] num, int begin, int end, int target,int newtarget,int firstnum) 
        {
            int l = begin, r = end;
            while (l < r)
            {
                if (num[l] + num[r] + target == newtarget) 
                {
                    ArrayList ans = new ArrayList();
                    ans.add(firstnum);//與原始的《3Sum》算法不同的地方為:記得把每次的啟示遍歷元素加入進去,就是4個數中的最小的那一個
                    ans.add(target);
                    ans.add(num[l]);
                    ans.add(num[r]);
                    ret.add(ans); //放入結果集中
                    while (l < r && num[l] == num[l+1]) l++;//避免結果重復,其後面和它相等的直接被跳過。
                    while (l < r && num[r] == num[r-1]) r--;////避免結果重復,其後面和它相等的直接被跳過。
                    l++;
                    r--;
                } 
                else if (num[l] + num[r] + target < newtarget) 
                    l++;
                else 
                    r--;
            }
        }
    }


     

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved