rename

OneCodeMonkey · OneCodeMonkey · commit 89b3b8589897 · 2019-07-30T11:43:03.000+08:00
diff --git a/leetcode_solved/leetcode_0018_4Sum.cpp b/leetcode_solved/leetcode_0018_4Sum.cpp
@@ -0,0 +1,58 @@
+class Solution {
+public:
+	/**
+	 * AC: 
+	 * Runtime: 48 ms, faster than 30.52% of C++ online submissions for 4Sum.
+	 * Memory Usage: 10.6 MB, less than 11.68% of C++ online submissions for 4Sum.
+	 *
+	 * 思路：先排序，然后以 O(n^2) 的复杂度做遍历，每一轮用两个游标缩小范围。
+	 * 总体复杂度：O(n^2)
+	 */
+    vector<vector<int>> fourSum(vector<int>& nums, int target) {
+     	vector<vector<int> >ret;
+     	int size = nums.size();
+     	if(size < 4)
+     		return vector<vector<int> >();
+
+     	// sort
+     	sort(nums.begin(), nums.end());
+
+     	for(int i = 0; i < size - 1; i++) {
+     		for(int j = i + 1; j < size; j++) {
+     			int l = j + 1;
+     			int r = size - 1;
+     			while(l < r) {
+     				int tempSum = nums[i] + nums[j] + nums[l] + nums[r];
+     				if(tempSum == target) {
+     					vector<int>tempArr;
+     					tempArr.push_back(nums[i]);
+     					tempArr.push_back(nums[j]);
+     					tempArr.push_back(nums[l]);
+     					tempArr.push_back(nums[r]);
+
+     					int flag = 0;
+     					for(auto it:ret) {
+     						if(it == tempArr) {
+     							flag = 1;
+                                break;
+     						}
+     					}
+                        if(flag) {
+                            l++;
+                            continue;
+                        }
+
+     					ret.push_back(tempArr);
+                        // break;       // 这里不应该直接退出，因为第三四个有可能有多种满足的组合
+                        l++;
+     				} else if(tempSum > target)
+     					r--;
+     				else if(tempSum < target)
+     					l++;
+     			}
+     		}
+     	}
+
+     	return ret;
+    }
+};
