# 2 暴力

``````List<List<Integer>> result = new ArrayList<>();
if (nums.length == 4 && nums[0] + nums[1] + nums[2] + nums[3] == target)
else if (nums.length > 4)
{
Arrays.sort(nums);
Set<List<Integer>> resultSet = new HashSet<>();
for(int i=0;i<nums.length-3;++i)
{
for(int j=i+1;j<nums.length-2;++j)
{
for(int k=j+1;k<nums.length-1;++k)
{
for(int m=k+1;m<nums.length;++m)
{
if(nums[i]+nums[j]+nums[k]+nums[m] == target)
}
}
}
}
Collections.sort(result,(t1,t2)->
{
if(t1.get(0) > t2.get(0))
return 1;
if (t1.get(0) < t2.get(0))
return -1;
if (t1.get(1) > t2.get(1))
return 1;
if (t1.get(1) < t2.get(1))
return -1;
if (t1.get(2) > t2.get(2))
return 1;
if (t1.get(2) < t2.get(2))
return -1;
if (t1.get(3) > t2.get(3))
return 1;
if (t1.get(3) < t2.get(3))
return -1;
return 0;
});
}
return result;
``````

# 3 优化

## 3.1 去掉结果排序

``````Collections.sort(result,(t1,t2)->
{
if(t1.get(0) > t2.get(0))
return 1;
if (t1.get(0) < t2.get(0))
return -1;
if (t1.get(1) > t2.get(1))
return 1;
if (t1.get(1) < t2.get(1))
return -1;
if (t1.get(2) > t2.get(2))
return 1;
if (t1.get(2) < t2.get(2))
return -1;
if (t1.get(3) > t2.get(3))
return 1;
if (t1.get(3) < t2.get(3))
return -1;
return 0;
});
``````

## 3.2 stream去重

``````return result.stream().distinct().collect(Collectors.toList());
``````

## 3.3 双指针+最大最小剪枝

``````for(int i=0;i<nums.length-3;++i)
{
for(int j=i+1;j<nums.length-2;++j)
{
int m = nums[i] + nums[j];
int left = j+1;
int right = nums.length-1;
while(left < right)
{
int temp = m + nums[left] + nums[right];
if(temp == target)
{
--right;
++left;
}
else if(temp > target)
--right;
else
++left;
}
}
}
``````

m为固定的数,left与right就是双指针,根据"三数"之和判断与目标值的大小移动双指针. 最小剪枝就是首先计算"三数"的最小值,若大于目标值就可以跳过,最大剪枝就是计算"三数"的最大值,若小于目标值则跳过,进入下一个循环:

``````int m = nums[i] + nums[j];
int left = j+1;
int right = nums.length-1;
if(m + nums[left] + nums[left+1] > target)
continue;
if (m + nums[right-1] + nums[right] < target)
continue;
``````

# 4 来来来再快一点

## 4.1 初始判断

``````List<List<Integer>> result = new ArrayList<>();
if (nums == null && nums.length < 4)
return result;
``````

## 4.2 一次不够,就再剪几次

``````Arrays.sort(nums);
int len = nums.length;
if(
nums[0] + nums[1] + nums[2] + nums[3] >  target
||
nums[len-4] + nums[len-3] + nums[len-2] + nums[len-1] < target
)
return result;
for(int i=0;i<len-3;++i)
``````

``````for(int i=0;i<len-3;++i)
{
if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target)
break;
if(nums[i] + nums[len-3] + nums[len-2] + nums[len-1] < target)
continue;
for(int j=i+1;j<len-2;++j)
}
``````

## 4.3 去重

### 4.3.1 双指针去重

``````result.add(Arrays.asList(nums[i], nums[j], nums[left++], nums[right--]));
while(left < right && nums[left] == nums[left-1])
++left;
while(left < right && nums[right] == nums[right+1])
--right;
``````

### 4.3.2 外循环去重

``````return result.stream().distinct().collect(Collectors.toList());
``````

``````[1,1,1,1,2,2,2,2],target=6
``````

``````[1,1,2,2]
``````

``````for(int i=0;i<len-2;++i)
if(i>0 && nums[i] == nums[i-1]) continue;
``````

``````for(int j=i+1;j<len-2;++j)
if(j > i+1 && nums[j] == nums[j-1]) continue;
``````

``````[1(a),1(b),1(c),1(d),2,2,2,2]
``````

``````if(i>0 && nums[i] == nums[i-1]) continue;
if(j>i + 1 && nums[j] == nums[j-1]) continue;
``````

github