GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Algorithm/leetcode_solved/leetcode_0018_4Sum.cpp at master · OneCodeMonkey/Algorithm Expand file tree/ Copy pathleetcode_0018_4Sum.cppMore file actions 58 lines (53 loc) · 1.62 KB / Copy pathleetcode_0018_4Sum.cppFile metadata and controls58 lines (53 loc) · 1.62 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 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; } }; |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |