[LeetCode]4Sum, 解题报告 - c++编程基础

前言

明天就要回京了，还是挺紧张的，今天还是要坚持的做做题目，看看android，晚上收拾一下行李，不得不说，家里还是很舒服的，尤其是搬了新家之后，我还有自己的书房，开心

上传一张图片，纪念一下，哎，博客写的越来越随意了

题目

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 Z http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcmRlci4gKGllLCBhIKHcIGIgodwgYyCh3CBkKTxicj4KVGhlIHNvbHV0aW9uIHNldCBtdXN0IG5vdCBjb250YWluIGR1cGxpY2F0ZSBxdWFkcnVwbGV0cy48YnI+Cgo8YnI+Cgo8aW1nIHNyYz0="https://www.cppentry.com/upload_files/article/49/1_fkzjr__.png" alt="\">

思路1

开始想的很简单，因为要求所有的组合，所以第一反应就是用DFS去解决这道题目，无奈 TLE，不过还是把DFS的代码贴出来，大家可以参考一下，也可以帮我改进一下

public class Solution {
    public static ArrayList
  
   > fourSum(int[] num, int target) {
        ArrayList
   
    > res = new ArrayList
    
     >(); if (num == null || num.length < 4) { return res; } Arrays.sort(num); ArrayList
     
       tmpStore = new ArrayList
      
       (); depthFS(0, 0, 0, num, target, tmpStore, res); return res; } public static void depthFS(int pos, int count, int sum, int[] num, int target, ArrayList
       
         tmpStore, ArrayList
        
         > res) { if (count == 4) { if (sum == target) { res.add(new ArrayList
         
          (tmpStore)); } } else { for (int i = pos; i < num.length && count < 4; i++) { if (sum + num[i] <= target) { tmpStore.add(num[i]); depthFS(i + 1, count + 1, sum + num[i], num, target, tmpStore, res); tmpStore.remove(tmpStore.size() - 1); } } } } }

思路2

这道题目其实可以直接用三个for循环解决

public class Solution {
    public static ArrayList
  
   > fourSum(int[] num, int target) {
        ArrayList
   
    > res = new ArrayList
    
     >(); if (num == null || num.length < 4) { return res; } Arrays.sort(num); HashSet
     
      > hashSet = new HashSet
      
       >(); for (int i = 0; i <= num.length - 4; i ++) { for (int j = i + 1; j <= num.length - 3; j ++) { for (int k = j + 1, h = num.length - 1; k < h;) { int sum = num[i] + num[j] + num[k] + num[h]; if (sum < target) { k ++; continue; } if (sum > target) { h --; continue; } ArrayList
       
         tmp = new ArrayList
        
         (); tmp.add(num[i]); tmp.add(num[j]); tmp.add(num[k]); tmp.add(num[h]); if (! hashSet.contains(tmp)) { hashSet.add(tmp); res.add(tmp); } k ++; h --; } } } return res; } }

后记

为什么要记录这道题目呢，因为思路1的DFS失败之后，我下意识的认为这是一道很牛逼的题目，是否需要用上动态规划+剪枝，因此我兴致勃勃的写下思路1之后开始思考思路2
中间看到了之前用双指针ac的Two sum题目，考虑这道题是否也可以用三个for循环搞定，坑爹啊，真的可以，所以就写了这篇博客