当前位置：首页 > news >正文

LeetCode -- 4Sum

news 来源：原创 2024/5/6 2:09:02

题目描述：

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<IList<int>> FourSum(int[] nums, int target) 
    {
        if(nums == null || nums.Length < 4){
    		return new List<IList<int>>();
    	}
    	
    	var dic = new Dictionary<string, List<int>>();
    	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<int>(){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<IList<int>>();
    	foreach(var kv in dic){
    		ret.Add(kv.Value);
    	}
    	
    	return ret;
    }
    
    
}

LeetCode -- Binary Tree Level Order Traversal II

（ZT）一个美国文科博士的YardLife

LeetCode -- Clone Graph

Oracle 中的nvl() 函数相当于Sql Server 的 isnull()

LeetCode -- Combinations

[IE编程] WebBrowser控件中设置页面的缩放

LeetCode -- Find the Duplicate Number

LeetCode -- Group Anagrams

LeetCode -- Kth Largest Element in an Array

相关文章：