You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
<
83DF
script type="application/json" data-target="react-app.embeddedData">{"payload":{"allShortcutsEnabled":false,"fileTree":{"algorithms/4Sum":{"items":[{"name":"4Sum.cpp","path":"algorithms/4Sum/4Sum.cpp","contentType":"file"}],"totalCount":1},"algorithms":{"items":[{"name":"3Sum","path":"algorithms/3Sum","contentType":"directory"},{"name":"3SumClosest","path":"algorithms/3SumClosest","contentType":"directory"},{"name":"4Sum","path":"algorithms/4Sum","contentType":"directory"},{"name":"LRUCache","path":"algorithms/LRUCache","contentType":"directory"},{"name":"addBinary","path":"algorithms/addBinary","contentType":"directory"},{"name":"addTwoNumbers","path":"algorithms/addTwoNumbers","contentType":"directory"},{"name":"anagrams","path":"algorithms/anagrams","contentType":"directory"},{"name":"balancedBinaryTree","path":"algorithms/balancedBinaryTree","contentType":"directory"},{"name":"bestTimeToBuyAndSellStock","path":"algorithms/bestTimeToBuyAndSellStock","contentType":"directory"},{"name":"binarySearchTreeIterator","path":"algorithms/binarySearchTreeIterator","contentType":"directory"},{"name":"binaryTreeInorderTraversal","path":"algorithms/binaryTreeInorderTraversal","contentType":"directory"},{"name":"binaryTreeLevelOrderTraversal","path":"algorithms/binaryTreeLevelOrderTraversal","contentType":"directory"},{"name":"binaryTreeMaximumPathSum","path":"algorithms/binaryTreeMaximumPathSum","contentType":"directory"},{"name":"binaryTreePostorderTraversal","path":"algorithms/binaryTreePostorderTraversal","contentType":"directory"},{"name":"binaryTreePreorderTraversal","path":"algorithms/binaryTreePreorderTraversal","contentType":"directory"},{"name":"binaryTreeRightSideView","path":"algorithms/binaryTreeRightSideView","contentType":"directory"},{"name":"binaryTreeUpsideDown","path":"algorithms/binaryTreeUpsideDown","contentType":"directory"},{"name":"binaryTreeZigzagLevelOrderTraversal","path":"algorithms/binaryTreeZigzagLevelOrderTraversal","contentType":"directory"},{"name":"candy","path":"algorithms/candy","contentType":"directory"},{"name":"climbStairs","path":"algorithms/climbStairs","contentType":"directory"},{"name":"cloneGraph","path":"algorithms/cloneGraph","contentType":"directory"},{"name":"combinationSum","path":"algorithms/combinationSum","contentType":"directory"},{"name":"combinations","path":"algorithms/combinations","contentType":"directory"},{"name":"compareVersionNumbers","path":"algorithms/compareVersionNumbers","contentType":"directory"},{"name":"constructBinaryTreeFromInorderAndPostorderTraversal","path":"algorithms/constructBinaryTreeFromInorderAndPostorderTraversal","contentType":"directory"},{"name":"constructBinaryTreeFromPreorderAndInorderTraversal","path":"algorithms/constructBinaryTreeFromPreorderAndInorderTraversal","contentType":"directory"},{"name":"containerWithMostWater","path":"algorithms/containerWithMostWater","contentType":"directory"},{"name":"convertSortedArrayToBinarySearchTree","path":"algorithms/convertSortedArrayToBinarySearchTree","contentType":"directory"},{"name":"convertSortedListToBinarySearchTree","path":"algorithms/convertSortedListToBinarySearchTree","contentType":"directory"},{"name":"copyListWithRandomPointer","path":"algorithms/copyListWithRandomPointer","contentType":"directory"},{"name":"countAndSay","path":"algorithms/countAndSay","contentType":"directory"},{"name":"decodeWays","path":"algorithms/decodeWays","contentType":"directory"},{"name":"distinctSubsequences","path":"algorithms/distinctSubsequences","contentType":"directory"},{"name":"divideTwoInt","path":"algorithms/divideTwoInt","contentType":"directory"},{"name":"dungeonGame","path":"algorithms/dungeonGame","contentType":"directory"},{"name":"editDistance","path":"algorithms/editDistance","contentType":"directory"},{"name":"evaluateReversePolishNotation","path":"algorithms/evaluateReversePolishNotation","contentType":"directory"},{"name":"excelSheetColumnNumber","path":"algorithms/excelSheetColumnNumber","contentType":"directory"},{"name":"excelSheetColumnTitle","path":"algorithms/excelSheetColumnTitle","contentType":"directory"},{"name":"factorialTrailingZeroes","path":"algorithms/factorialTrailingZeroes","contentType":"directory"},{"name":"findMinimumInRotatedSortedArray","path":"algorithms/findMinimumInRotatedSortedArray","contentType":"directory"},{"name":"findPeakElement","path":"algorithms/findPeakElement","contentType":"directory"},{"name":"firstMissingPositive","path":"algorithms/firstMissingPositive","contentType":"directory"},{"name":"flattenBinaryTreeToLinkedList","path":"algorithms/flattenBinaryTreeToLinkedList","contentType":"directory"},{"name":"fractionToRecurringDecimal","path":"algorithms/fractionToRecurringDecimal","contentType":"directory"},{"name":"gasStation","path":"algorithms/gasStation","contentType":"directory"},{"name":"generateParentheses","path":"algorithms/generateParentheses","contentType":"directory"},{"name":"grayCode","path":"algorithms/grayCode","contentType":"directory"},{"name":"houseRobber","path":"algorithms/houseRobber","contentType":"directory"},{"name":"insertInterval","path":"algorithms/insertInterval","contentType":"directory"},{"name":"insertionSortList","path":"algorithms/insertionSortList","contentType":"directory"},{"name":"integerToRoman","path":"algorithms/integerToRoman","contentType":"directory"},{"name":"interleavingString","path":"algorithms/interleavingString","contentType":"directory"},{"name":"intersectionOfTwoLinkedLists","path":"algorithms/intersectionOfTwoLinkedLists","contentType":"directory"},{"name":"jumpGame","path":"algorithms/jumpGame","contentType":"directory"},{"name":"largestNumber","path":"algorithms/largestNumber","contentType":"directory"},{"name":"largestRectangleInHistogram","path":"algorithms/largestRectangleInHistogram","contentType":"directory"},{"name":"lengthOfLastWord","path":"algorithms/lengthOfLastWord","contentType":"directory"},{"name":"letterCombinationsOfAPhoneNumber","path":"algorithms/letterCombinationsOfAPhoneNumber","contentType":"directory"},{"name":"linkedListCycle","path":"algorithms/linkedListCycle","contentType":"directory"},{"name":"longestCommonPrefix","path":"algorithms/longestCommonPrefix","contentType":"directory"},{"name":"longestConsecutiveSequence","path":"algorithms/longestConsecutiveSequence","contentType":"directory"},{"name":"longestPalindromicSubstring","path":"algorithms/longestPalindromicSubstring","contentType":"directory"},{"name":"longestSubstringWithAtMostTwoDistinctCharacters","path":"algorithms/longestSubstringWithAtMostTwoDistinctCharacters","contentType":"directory"},{"name":"longestSubstringWithoutRepeatingCharacters","path":"algorithms/longestSubstringWithoutRepeatingCharacters","contentType":"directory"},{"name":"longestValidParentheses","path":"algorithms/longestValidParentheses","contentType":"directory"},{"name":"majorityElement","path":"algorithms/majorityElement","contentType":"directory"},{"name":"maxPointsOnALine","path":"algorithms/maxPointsOnALine","contentType":"directory"},{"name":"maximalRectangle","path":"algorithms/maximalRectangle","contentType":"directory"},{"name":"maximumDepthOfBinaryTree","path":"algorithms/maximumDepthOfBinaryTree","contentType":"directory"},{"name":"maximumGap","path":"algorithms/maximumGap","contentType":"directory"},{"name":"maximumProductSubarray","path":"algorithms/maximumProductSubarray","contentType":"directory"},{"name":"maximumSubArray","path":"algorithms/maximumSubArray","contentType":"directory"},{"name":"medianOfTwoSortedArrays","path":"algorithms/medianOfTwoSortedArrays","contentType":"directory"},{"name":"mergeIntervals","path":"algorithms/mergeIntervals","contentType":"directory"},{"name":"mergeKSortedLists","path":"algorithms/mergeKSortedLists","contentType":"directory"},{"name":"mergeTwoSortedArray","path":"algorithms/mergeTwoSortedArray","contentType":"directory"},{"name":"mergeTwoSortedList","path":"algorithms/mergeTwoSortedList","contentType":"directory"},{"name":"minStack","path":"algorithms/minStack","contentType":"directory"},{"name":"minimumDepthOfBinaryTree","path":"algorithms/minimumDepthOfBinaryTree","contentType":"directory"},{"name":"minimumPathSum","path":"algorithms/minimumPathSum","contentType":"directory"},{"name":"minimumWindowSubstring","path":"algorithms/minimumWindowSubstring","contentType":"directory"},{"name":"missingRanges","path":"algorithms/missingRanges","contentType":"directory"},{"name":"multiplyStrings","path":"algorithms/multiplyStrings","contentType":"directory"},{"name":"nQueens","path":"algorithms/nQueens","contentType":"directory"},{"name":"nextPermutation","path":"algorithms/nextPermutation","contentType":"directory"},{"name":"numberOf1Bits","path":"algorithms/numberOf1Bits","contentType":"directory"},{"name":"oneEditDistance","path":"algorithms/oneEditDistance","contentType":"directory"},{"name":"palindromeNumber","path":"algorithms/palindromeNumber","contentType":"directory"},{"name":"palindromePartitioning","path":"algorithms/palindromePartitioning","contentType":"directory"},{"name":"partitionList","path":"algorithms/partitionList","contentType":"directory"},{"name":"pascalTriangle","path":"algorithms/pascalTriangle","contentType":"directory"},{"name":"pathSum","path":"algorithms/pathSum","contentType":"directory"},{"name":"permutationSequence","path":"algorithms/permutationSequence","contentType":"directory"},{"name":"permutations","path":"algorithms/permutations","contentType":"directory"},{"name":"plusOne","path":"algorithms/plusOne","contentType":"directory"},{"name":"populatingNextRightPointersInEachNode","path":"algorithms/populatingNextRightPointersInEachNode","contentType":"directory"},{"name":"pow","path":"algorithms/pow","contentType":"directory"},{"name":"readNCharactersGivenRead4","path":"algorithms/readNCharactersGivenRead4","contentType":"directory"},{"name":"recoverBinarySearchTree","path":"algorithms/recoverBinarySearchTree","contentType":"directory"},{"name":"regularExpressionMatching","path":"algorithms/regularExpressionMatching","contentType":"directory"},{"name":"removeDuplicatesFromSortedArray","path":"algorithms/removeDuplicatesFromSortedArray","contentType":"directory"},{"name":"removeDuplicatesFromSortedList","path":"algorithms/removeDuplicatesFromSortedList","contentType":"directory"},{"name":"removeElement","path":"algorithms/removeElement","contentType":"directory"},{"name":"removeNthNodeFromEndOfList","path":"algorithms/removeNthNodeFromEndOfList","contentType":"directory"},{"name":"reorderList","path":"algorithms/reorderList","contentType":"directory"},{"name":"repeatedDNASequences","path":"algorithms/repeatedDNASequences","contentType":"directory"},{"name":"restoreIPAddresses","path":"algorithms/restoreIPAddresses","contentType":"directory"},{"name":"reverseBits","path":"algorithms/reverseBits","contentType":"directory"},{"name":"reverseInteger","path":"algorithms/reverseInteger","contentType":"directory"},{"name":"reverseLinkedList","path":"algorithms/reverseLinkedList","contentType":"directory"},{"name":"reverseNodesInKGroup","path":"algorithms/reverseNodesInKGroup","contentType":"directory"},{"name":"reverseWordsInAString","path":"algorithms/reverseWordsInAString","contentType":"directory"},{"name":"romanToInteger","path":"algorithms/romanToInteger","contentType":"directory"},{"name":"rotateArray","path":"algorithms/rotateArray","contentType":"directory"},{"name":"rotateImage","path":"algorithms/rotateImage","contentType":"directory"},{"name":"rotateList","path":"algorithms/rotateList","contentType":"directory"},{"name":"sameTree","path":"algorithms/sameTree","contentType":"directory"},{"name":"scrambleString","path":"algorithms/scrambleString","contentType":"directory"},{"name":"search2DMatrix","path":"algorithms/search2DMatrix","contentType":"directory"},{"name":"searchForRange","path":"algorithms/searchForRange","contentType":"directory"},{"name":"searchInRotatedSortedArray","path":"algorithms/searchInRotatedSortedArray","contentType":"directory"},{"name":"searchInsertPosition","path":"algorithms/searchInsertPosition","contentType":"directory"},{"name":"setMatrixZeroes","path":"algorithms/setMatrixZeroes","contentType":"directory"},{"name":"simplifyPath","path":"algorithms/simplifyPath","contentType":"directory"},{"name":"singleNumber","path":"algorithms/singleNumber","contentType":"directory"},{"name":"sortColors","path":"algorithms/sortColors","contentType":"directory"},{"name":"sortList","path":"algorithms/sortList","contentType":"directory"},{"name":"spiralMatrix","path":"algorithms/spiralMatrix","contentType":"directory"},{"name":"sqrt","path":"algorithms/sqrt","contentType":"directory"},{"name":"strStr","path":"algorithms/strStr","contentType":"directory"},{"name":"stringToIntegerAtoi","path":"algorithms/stringToIntegerAtoi","contentType":"directory"},{"name":"subsets","path":"algorithms/subsets","contentType":"directory"},{"name":"substringWithConcatenationOfAllWords","path":"algorithms/substringWithConcatenationOfAllWords","contentType":"directory"},{"name":"sudokuSolver","path":"algorithms/sudokuSolver","contentType":"directory"},{"name":"sumRootToLeafNumber","path":"algorithms/sumRootToLeafNumber","contentType":"directory"},{"name":"surroundedRegions","path":"algorithms/surroundedRegions","contentType":"directory"},{"name":"swapNodesInPairs","path":"algorithms/swapNodesInPairs","contentType":"directory"},{"name":"symmetricTree","path":"algorithms/symmetricTree","contentType":"directory"},{"name":"textJustification","path":"algorithms/textJustification","contentType":"directory"},{"name":"trappingRainWater","path":"algorithms/trappingRainWater","contentType":"directory"},{"name":"triangle","path":"algorithms/triangle","contentType":"directory"},{"name":"twoSum","path":"algorithms/twoSum","contentType":"directory"},{"name":"uniqueBinarySearchTrees","path":"algorithms/uniqueBinarySearchTrees","contentType":"directory"},{"name":"uniquePaths","path":"algorithms/uniquePaths","contentType":"directory"},{"name":"validNumber","path":"algorithms/validNumber","contentType":"directory"},{"name":"validPalindrome","path":"algorithms/validPalindrome","contentType":"directory"},{"name":"validParentheses","path":"algorithms/validParentheses","contentType":"directory"},{"name":"validSudoku","path":"algorithms/validSudoku","contentType":"directory"},{"name":"validateBinarySearchTree","path":"algorithms/validateBinarySearchTree","contentType":"directory"},{"name":"wildcardMatching","path":"algorithms/wildcardMatching","contentType":"directory"},{"name":"wordBreak","path":"algorithms/wordBreak","contentType":"directory"},{"name":"wordLadder","path":"algorithms/wordLadder","contentType":"directory"},{"name":"wordSearch","path":"algorithms/wordSearch","contentType":"directory"},{"name":"zigZagConversion","path":"algorithms/zigZagConversion","contentType":"directory"}],"totalCount":155},"":{"items":[{"name":"algorithms","path":"algorithms","contentType":"directory"},{"name":"scripts","path":"scripts","contentType":"directory"},{"name":"shell","path":"shell","contentType":"directory"},{"name":"README.md","path":"README.md","contentType":"file"}],"totalCount":4}},"fileTreeProcessingTime":23.395936,"foldersToFetch":[],"incompleteFileTree":false,"repo":{"id":34207631,"defaultBranch":"master","name":"leetcode","ownerLogin":"pxjw","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2015-04-19T13:27:05.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/5189169?v=4","public":true,"private":false,"isOrgOwned":false},"codeLineWrapEnabled":false,"symbolsExpanded":false,"treeExpanded":true,"refInfo":{"name":"master","listCacheKey":"v0:1621021058.763218","canEdit":false,"refType":"branch","currentOid":"407b5bae7b4905f5d7de88d93c8aba6d9dd16abf"},"path":"algorithms/4Sum/4Sum.cpp","currentUser":null,"blob":{"rawLines":["// Source : https://oj.leetcode.com/problems/4sum/","// Author : Hao Chen","// Date : 2014-07-03","","/********************************************************************************** ","* ","* 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)","* ","* ","**********************************************************************************/","","#include \u003ciostream\u003e","#include \u003cvector\u003e","#include \u003calgorithm\u003e","using namespace std;","","vector\u003cvector\u003cint\u003e \u003e threeSum(vector\u003cint\u003e num, int target); ","","/*"," * 1) Sort the array,"," * 2) traverse the array, and solve the problem by using \"3Sum\" soultion."," */","","vector\u003cvector\u003cint\u003e \u003e fourSum(vector\u003cint\u003e \u0026num, int target) {"," vector\u003c vector\u003cint\u003e \u003e result;"," if (num.size()\u003c4) return result;"," sort( num.begin(), num.end() );"," "," for(int i=0; i\u003cnum.size()-3; i++) {"," //skip the duplication"," if (i\u003e0 \u0026\u0026 num[i-1]==num[i]) continue;"," vector\u003cint\u003e n(num.begin()+i+1, num.end());"," vector\u003cvector\u003cint\u003e \u003e ret = threeSum(n, target-num[i]);"," for(int j=0; j\u003cret.size(); j++){"," ret[j].insert(ret[j].begin(), num[i]);"," result.push_back(ret[j]);"," }"," }",""," return result; ","}","","vector\u003cvector\u003cint\u003e \u003e threeSum(vector\u003cint\u003e num, int target) {",""," vector\u003c vector\u003cint\u003e \u003e result;"," //sort the array (if the qrray is sorted already, it won't waste any time)"," sort(num.begin(), num.end());",""," int n = num.size();",""," for (int i=0; i\u003cn-2; i++) {"," //skip the duplication"," if (i\u003e0 \u0026\u0026 num[i-1]==num[i]) continue;"," int a = num[i];"," int low = i+1;"," int high = n-1;"," while ( low \u003c high ) {"," int b = num[low];"," int c = num[high];"," if (a+b+c == target) {"," //got the soultion"," vector\u003cint\u003e v;"," v.push_back(a);"," v.push_back(b);"," v.push_back(c);"," result.push_back(v);"," // Continue search for all triplet combinations summing to zero."," //skip the duplication"," while(low\u003cn \u0026\u0026 num[low]==num[low+1]) low++;"," while(high\u003e0 \u0026\u0026 num[high]==num[high-1]) high--;"," low++;"," high--;"," } else if (a+b+c \u003e target) {"," //skip the duplication"," while(high\u003e0 \u0026\u0026 num[high]==num[high-1]) high--;"," high--;"," } else{"," //skip the duplication"," while(low\u003cn \u0026\u0026 num[low]==num[low+1]) low++;"," low++;"," }"," }"," }"," return result;","}","","","int printMatrix(vector\u003c vector\u003cint\u003e \u003e \u0026vv)","{"," for(int i=0; i\u003cvv.size(); i++) {"," cout \u003c\u003c \"[\";"," for(int j=0; j\u003cvv[i].size(); j++) {"," cout \u003c\u003c \" \" \u003c\u003c vv[i][j];"," }"," cout \u003c\u003c \"]\" \u003c\u003c endl;;"," }","}","","","int main()","{"," int a[] = {1,0,-1,0,-2,2};"," vector\u003cint\u003e n(a, a+6);"," int t = 0;"," vector\u003c vector\u003cint\u003e \u003e v = fourSum(n, t);"," printMatrix(v);",""," n.clear();"," int b[] = {-1,-5,-5,-3,2,5,0,4};"," n.insert(n.begin(), b, b+8);"," t = -7;"," v = fourSum(n, t);"," printMatrix(v);",""," return 0;","}"],"stylingDirectives":null,"colorizedLines":null,"csv":null,"csvError":null,"dependabotInfo":{"showConfigurationBanner":false,"configFilePath":null,"networkDependabotPath":"/pxjw/leetcode/network/updates","dismissConfigurationNoticePath":"/settings/dismiss-notice/dependabot_configuration_notice","configurationNoticeDismissed":null},"displayName":"4Sum.cpp","displayUrl":"https://github.com/pxjw/leetcode/blob/master/algorithms/4Sum/4Sum.cpp?raw=true","headerInfo":{"blobSize":"3.48 KB","deleteTooltip":"You must be signed in to make or propose changes","editTooltip":"You must be signed in to make or propose changes","ghDesktopPath":"https://desktop.github.com","isGitLfs":false,"onBranch":true,"shortPath":"e067baf","siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fpxjw%2Fleetcode%2Fblob%2Fmaster%2Falgorithms%2F4Sum%2F4Sum.cpp","isCSV":false,"isRichtext":false,"toc":null,"lineInfo":{"truncatedLoc":"129","truncatedSloc":"112"},"mode":"file"},"image":false,"isCodeownersFile":null,"isPlain":false,"isValidLegacyIssueTemplate":false,"issueTemplate":null,"discussionTemplate":null,"language":"C++","languageID":43,"large":false,"planSupportInfo":{"repoIsFork":null,"repoOwnedByCurrentUser":null,"requestFullPath":"/pxjw/leetcode/blob/master/algorithms/4Sum/4Sum.cpp","showFreeOrgGatedFeatureMessage":null,"showPlanSupportBanner":null,"upgradeDataAttributes":null,"upgradePath":null},"publishBannersInfo":{"dismissActionNoticePath":"/settings/dismiss-notice/publish_action_from_dockerfile","releasePath":"/pxjw/leetcode/releases/new?marketplace=true","showPublishActionBanner":false},"rawBlobUrl":"https://github.com/pxjw/leetcode/raw/refs/heads/master/algorithms/4Sum/4Sum.cpp","renderImageOrRaw":false,"richText":null,"renderedFileInfo":null,"shortPath":null,"symbolsEnabled":true,"tabSize":8,"topBannersInfo":{"overridingGlobalFundingFile":false,"globalPreferredFundingPath":null,"showInvalidCitationWarning":false,"citationHelpUrl":"https://docs.github.com/github/creating-cloning-and-archiving-repositories/creating-a-repository-on-github/about-citation-files","actionsOnboardingTip":null},"truncated":false,"viewable":true,"workflowRedirectUrl":null,"symbols":null},"copilotInfo":null,"copilotAccessAllowed":false,"modelsAccessAllowed":false,"modelsRepoIntegrationEnabled":false,"csrf_tokens":{"/pxjw/leetcode/branches":{"post":"v0TT52SlGo9AMlTySN87O9RiPXFNHPz5xkL1qcQBlPtweTq1l5dYsrOtit6_0edZlV3zblFZds-rjDQMLslZqw"},"/repos/preferences":{"post":"MfcFP9Lb5x2Vk8CO5WusiTHuSmEW1dd7IdtgYiGafKAgTFSSytnaPHvJirftg_zVIw296F2ZMm4pzlOLQUB13A"}}},"title":"leetcode/algorithms/4Sum/4Sum.cpp at master · pxjw/leetcode","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1b17b3e7786a.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}