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)我的答案:
public class Solution { public IList<IList<int>> FourSum(int[] nums, int target) { List<IList<int>> result = new List<IList<int>>(); Array.Sort(nums); ;i<nums.Length-;i++) { ||nums[i]!=nums[i-]) { ;m<nums.Length-;m++) { || (nums[m]!=nums[m-]) ) { ; ; ; while(j<k) { List<int> res=new List<int>(); sum=nums[i]+nums[j]+nums[k]+nums[m]; if (sum==target) { ]{nums[i],nums[m],nums[j],nums[k]}; res.AddRange(ints); result.Add(res); ]) k--; ]) j++; k--; j++; } else if (sum>target) k--; else j++; } } } } } return result; } }
总结:
1 这个答案虽然可以Accepted,但是运行时间太慢
2 int[] ints=new int[4]{nums[i],nums[m],nums[j],nums[k]}; res.AddRange(ints); 利用这两句可以向List中批量添加数据
3 Array.Sort(nums);可以直接对数组排序。
4 这个算法是在sum3的基础上改进的,在第二层for循环中要有条件(m-i)==1;确保当i!=0时候,就算m=i+1&&nums[m]==nums[i]的时候,也能进入if语句中
第二种,也是效率更高更好理解的一种方法,建议掌握这种方法,因为这种方法很容易可以迁移到其他个数相加的类似问题中:
public class Solution { public IList<IList<int>> FourSum(int[] nums, int target) { List<IList<int>> result = new List<IList<int>>(); Array.Sort(nums); ;i<nums.Length-;i++) { int target_3=target- nums[i]; ;j<nums.Length-;j++) { int target_2=target_3- nums[j]; ,back=nums.Length-; while(front<back) { int sum=nums[front]+nums[back]; if(sum>target_2) back--; else if (sum<target_2) front ++; else { List<int> res=new List<int>(); ]{nums[i],nums[j],nums[front],nums[back]}; res.AddRange(ints); result.Add(res); ]) front++; ]) back--; front++; back--; } } <nums.Length-&&nums[j]==nums[j+]) j++; } <nums.Length-&&nums[i]==nums[i+]) i++; } return result; } }