LeetCode -- 4Sum

LeetCode -- 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)


在數組中找到四個數和=target。


和3Sum思路一模一樣，就是外面多加了一層循環。


實現代碼：

public class Solution {
    public IList> FourSum(int[] nums, int target) 
    {
        if(nums == null || nums.Length < 4){
    		return new List>();
    	}
    	
    	var dic = new Dictionary>();
    	var list = nums.OrderBy(x=>x).ToList();
    	
    	var len = list.Count;
    	for(var j = 0;j < len ; j++)
    	{
    		var d = list[j];
    		for (var i = 0 ;i <= len - 3 ;i++)
    		{	
    			var a = list[i];
    			var start = i+1;
    			var end = len-1;
    			if(i == j){
    				continue;
    			}
    			
    			while (start < end)
    			{
    				if(start == j){
    					start ++; 
    					continue;
    				}
    				if(end == j){
    					end --;
    					continue;
    				}
    				
    				var b = list[start];
    				var c = list[end];
    				
    				if (a+b+c+d == target) {
    
    					var v = new List(){a,b,c,d}.OrderBy(x=>x).ToList();
    					var k = string.Join(",",v);
    					if(!dic.ContainsKey(k)){
    						dic.Add(k,v);
    					}
    					start ++;
    					end --;
    				}
    				else if (a+b+c+d > target){
    					end --;
    				}
    				else{
    					start ++;
    				}
    			}
    		}
    	}
    	
    	
    	var ret = new List>();
    	foreach(var kv in dic){
    		ret.Add(kv.Value);
    	}
    	
    	return ret;
    }
    
    
}