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
{"payload":{"allShortcutsEnabled":false,"path":"Two-Sum Problem","repo":{"id":192920672,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"devatef","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2019-06-20T12:59:53.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/2884690?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"Permutations","listCacheKey":"v0:1619202172.190729","canEdit":false,"refType":"branch","currentOid":"3f409c5bcc966326b951a13e3a7ba1f81ab72871"},"tree":{"items":[{"name":"Solution 1/2Sum.playground","path":"Two-Sum Problem/Solution 1/2Sum.playground","contentType":"directory","hasSimplifiedPath":true},{"name":"Solution 2/2Sum.playground","path":"Two-Sum Problem/Solution 2/2Sum.playground","contentType":"directory","hasSimplifiedPath":true},{"name":"README.markdown","path":"Two-Sum Problem/README.markdown","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.markdown","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eTwo-Sum Problem\u003c/h1\u003e\u003ca id=\"user-content-two-sum-problem\" class=\"anchor\" aria-label=\"Permalink: Two-Sum Problem\" href=\"#two-sum-problem\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eGiven an array of integers and an integer target, return the indices of two numbers that add up to the target.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThere are a variety of solutions to this problem (some better than others). The following solutions both run in \u003cstrong\u003eO(n)\u003c/strong\u003e time.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSolution 1\u003c/h1\u003e\u003ca id=\"user-content-solution-1\" class=\"anchor\" aria-label=\"Permalink: Solution 1\" href=\"#solution-1\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis solution looks at one number at a time, storing each number in the dictionary. It uses the number as the key and the number's index in the array as the value.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eFor each number n, we know the complementing number to sum up to the target is \u003ccode\u003etarget - n\u003c/code\u003e. By looking up the complement in the dictionary, we'd know whether we've seen the complement before and what its index is.\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func twoSum(_ nums: [Int], target: Int) -\u0026gt; (Int, Int)? {\n var dict = [Int: Int]()\n \n // For every number n,\n for (currentIndex, n) in nums.enumerated() {\n // Find the complement to n that would sum up to the target.\n let complement = target - n\n \n // Check if the complement is in the dictionary.\n if let complementIndex = dict[complement] {\n return (complementIndex, currentIndex)\n }\n \n // Store n and its index into the dictionary.\n dict[n] = currentIndex\n }\n \n return nil\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e twoSum\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ nums\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e target\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u003cspan class=\"pl-c1\"\u003e?\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003edict\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eInt\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e Int\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \n // For every number n,\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e\u003cspan class=\"pl-s1\"\u003e(currentIndex\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e n\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e nums\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eenumerated\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n // Find the complement to n that would sum up to the target.\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ecomplement\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e target \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e n\n \n // Check if the complement is in the dictionary.\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e complementIndex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003edict\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ecomplement\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ecomplementIndex\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e currentIndex\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \n // Store n and its index into the dictionary.\n \u003cspan class=\"pl-en\"\u003edict\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003en\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e currentIndex\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003enil\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ccode\u003etwoSum\u003c/code\u003e function takes two parameters: the \u003ccode\u003enumbers\u003c/code\u003e array and the target sum. It returns the two indicies of the pair of elements that sums up to the target, or \u003ccode\u003enil\u003c/code\u003e if they can't be found.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's run through the algorithm to see how it works. Given the array:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"[3, 2, 9, 8]\"\u003e\u003cpre\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e9\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eLet's find out if there exist two entries whose sum is 10.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eInitially, our dictionary is empty. We begin looping through each element:\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003cstrong\u003ecurrentIndex = 0\u003c/strong\u003e | n = nums[0] = 3 | complement = 10 - 3 = 7\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003eIs the complement \u003ccode\u003e7\u003c/code\u003e in the dictionary? No, so we add \u003ccode\u003e3\u003c/code\u003e and its index \u003ccode\u003e0\u003c/code\u003e to the dictionary.\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"[3: 0]\"\u003e\u003cpre\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003cstrong\u003ecurrentIndex = 1\u003c/strong\u003e | n = 2 | complement = 10 - 2 = 8\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003eIs the complement \u003ccode\u003e8\u003c/code\u003e in the dictionary? No, so we add \u003ccode\u003e2\u003c/code\u003e and its index \u003ccode\u003e1\u003c/code\u003e to the dictionary.\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"[3: 0, 2: 1]\"\u003e\u003cpre\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003cstrong\u003ecurrentIndex = 2\u003c/strong\u003e | n = 9 | complement = 10 - 9 = 1\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003eIs the complement \u003ccode\u003e1\u003c/code\u003e in the dictionary? No, so we add \u003ccode\u003e9\u003c/code\u003e and its index \u003ccode\u003e2\u003c/code\u003e to the dictionary.:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"[3: 0, 2: 1, 9: 2]\"\u003e\u003cpre\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e9\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003cstrong\u003ecurrentIndex = 3\u003c/strong\u003e | n = 8 | complement = 10 - 8 = 2\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003eIs the complement \u003ccode\u003e2\u003c/code\u003e in the dictionary? Yes! That means that we have found a pair of entries that sum to the target!\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eTherefore, the \u003ccode\u003ecomplementIndex = dict[2] = 1\u003c/code\u003e and the \u003ccode\u003ecurrentIndex = 3\u003c/code\u003e. The tuple we return is \u003ccode\u003e(1, 3)\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIf the given array has multiple solutions, only the first solution is returned.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe running time of this algorithm is \u003cstrong\u003eO(n)\u003c/strong\u003e because it may look at every element in the array. It also requires \u003cstrong\u003eO(n)\u003c/strong\u003e additional storage space for the dictionary.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSolution 2\u003c/h1\u003e\u003ca id=\"user-content-solution-2\" class=\"anchor\" aria-label=\"Permalink: Solution 2\" href=\"#solution-2\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eNote\u003c/strong\u003e: This particular algorithm requires that the array is sorted, so if the array isn't sorted yet (usually it won't be), you need to sort it first. The time complexity of the algorithm itself is \u003cstrong\u003eO(n)\u003c/strong\u003e and, unlike the previous solution, it does not require extra storage. Of course, if you have to sort first, the total time complexity becomes \u003cstrong\u003eO(n log n)\u003c/strong\u003e. Slightly worse but still quite acceptable.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is the code in Swift:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func twoSumProblem(_ a: [Int], k: Int) -\u0026gt; ((Int, Int))? {\n var i = 0\n var j = a.count - 1\n\n while i \u0026lt; j {\n let sum = a[i] + a[j]\n if sum == k {\n return (i, j)\n } else if sum \u0026lt; k {\n i += 1\n } else {\n j -= 1\n }\n }\n return nil\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e twoSumProblem\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e k\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u003cspan class=\"pl-c1\"\u003e?\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ej\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e a\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e i \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e j \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esum\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e a\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ej\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e sum \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e k \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e j\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e sum \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e k \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n i \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n j \u003cspan class=\"pl-c1\"\u003e-=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003enil\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAs in the first solution, the \u003ccode\u003etwoSumProblem()\u003c/code\u003e function takes as parameters the array \u003ccode\u003ea\u003c/code\u003e with the numbers and \u003ccode\u003ek\u003c/code\u003e, the sum we're looking for. If there are two numbers that add up to \u003ccode\u003ek\u003c/code\u003e, the function returns a tuple containing their array indices. If not, it returns \u003ccode\u003enil\u003c/code\u003e. The main difference is that \u003ccode\u003ea\u003c/code\u003e is assumed to be sorted.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eTo test it, copy the code into a playground and add the following:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"let a = [2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100]\nif let (i, j) = twoSumProblem(a, k: 33) {\n a[i] + a[j] // 33\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ea\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e4\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e4\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e7\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e9\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e10\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e12\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e14\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e21\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e22\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e100\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e j\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003etwoSumProblem\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e k\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e33\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e a\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ej\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e // 33\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis returns the tuple \u003ccode\u003e(8, 10)\u003c/code\u003e because \u003ccode\u003ea[8] = 12\u003c/code\u003e and \u003ccode\u003ea[10] = 21\u003c/code\u003e, and together they add up to \u003ccode\u003e33\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eSo how does this algorithm work? It takes advantage of the array being sorted. That's true for many algorithms, by the way. If you first sort the data, it's often easier to perform your calculations.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIn the example, the sorted array is:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe algorithm uses the two variables \u003ccode\u003ei\u003c/code\u003e and \u003ccode\u003ej\u003c/code\u003e to point to the beginning and end of the array, respectively. Then it increments \u003ccode\u003ei\u003c/code\u003e and decrements \u003ccode\u003ej\u003c/code\u003e until the two meet. While it's doing this, it checks whether \u003ccode\u003ea[i]\u003c/code\u003e and \u003ccode\u003ea[j]\u003c/code\u003e add up to \u003ccode\u003ek\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's step through this. Initially, we have:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe sum of these two is \u003ccode\u003e2 + 100 = 102\u003c/code\u003e. That's obviously too much, since \u003ccode\u003ek = 33\u003c/code\u003e in this example. There is no way that \u003ccode\u003e100\u003c/code\u003e will ever be part of the answer, so decrement \u003ccode\u003ej\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWe have:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe sum is \u003ccode\u003e2 + 22 = 24\u003c/code\u003e. Now the sum is too small. We can safely conclude at this point that the number \u003ccode\u003e2\u003c/code\u003e will never be part of the answer. The largest number on the right is \u003ccode\u003e22\u003c/code\u003e, so we at least need \u003ccode\u003e11\u003c/code\u003e on the left to make \u003ccode\u003e33\u003c/code\u003e. Anything less than \u003ccode\u003e11\u003c/code\u003e is not going to cut it. (This is why we sorted the array!)\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eSo, \u003ccode\u003e2\u003c/code\u003e is out and we increment \u003ccode\u003ei\u003c/code\u003e to look at the next small number.\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe sum is \u003ccode\u003e3 + 22 = 25\u003c/code\u003e. Still too small, so increment \u003ccode\u003ei\u003c/code\u003e again.\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eIn fact, we have to increment \u003ccode\u003ei\u003c/code\u003e a few more times, until we get to \u003ccode\u003e12\u003c/code\u003e:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNow the sum is \u003ccode\u003e12 + 22 = 34\u003c/code\u003e. It's too high, which means we need to decrement \u003ccode\u003ej\u003c/code\u003e. This gives:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]\n i j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAnd finally, we have the answer: \u003ccode\u003e12 + 21 = 33\u003c/code\u003e. Yay!\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIt's possible, of course, that there are no values for \u003ccode\u003ea[i] + a[j]\u003c/code\u003e that sum to \u003ccode\u003ek\u003c/code\u003e. In that case, eventually \u003ccode\u003ei\u003c/code\u003e and \u003ccode\u003ej\u003c/code\u003e will point at the same number. Then we can conclude that no answer exists and we return \u003ccode\u003enil\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eI'm quite enamored by this little algorithm. It shows that with some basic preprocessing on the input data -- sorting it from low to high -- you can turn a tricky problem into a very simple and beautiful algorithm.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eAdditional Reading\u003c/h2\u003e\u003ca id=\"user-content-additional-reading\" class=\"anchor\" aria-label=\"Permalink: Additional Reading\" href=\"#additional-reading\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003ca href=\"https://github.com/raywenderlich/swift-algorithm-club/tree/master/3Sum%20and%204Sum\"\u003e3Sum / 4Sum\u003c/a\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eWritten for Swift Algorithm Club by Matthijs Hollemans and Daniel Speiser\u003c/em\u003e\u003c/p\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Two-Sum Problem","anchor":"two-sum-problem","htmlText":"Two-Sum Problem"},{"level":1,"text":"Solution 1","anchor":"solution-1","htmlText":"Solution 1"},{"level":1,"text":"Solution 2","anchor":"solution-2","htmlText":"Solution 2"},{"level":2,"text":"Additional Reading","anchor":"additional-reading","htmlText":"Additional Reading"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fdevatef%2Fswift-algorithm-club%2Ftree%2FPermutations%2FTwo-Sum%2520Problem"}},"totalCount":3,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","contentType":"directory"},{"name":"AVL Tree","path":"AVL Tree","contentType":"directory"},{"name":"All-Pairs Shortest Paths","path":"All-Pairs Shortest Paths","contentType":"directory"},{"name":"Array2D","path":"Array2D","contentType":"directory"},{"name":"B-Tree","path":"B-Tree","contentType":"directory"},{"name":"Binary Search Tree","path":"Binary Search Tree","contentType":"directory"},{"name":"Binary Search","path":"Binary Search","contentType":"directory"},{"name":"Binary Tree","path":"Binary Tree","contentType":"directory"},{"name":"Bit Set","path":"Bit Set","contentType":"directory"},{"name":"Bloom Filter","path":"Bloom Filter","contentType":"directory"},{"name":"Bounded Priority Queue","path":"Bounded
4C91
Priority Queue","contentType":"directory"},{"name":"Boyer-Moore-Horspool","path":"Boyer-Moore-Horspool","contentType":"directory"},{"name":"Breadth-First Search","path":"Breadth-First Search","contentType":"directory"},{"name":"Brute-Force String Search","path":"Brute-Force String Search","contentType":"directory"},{"name":"Bubble Sort","path":"Bubble Sort","contentType":"directory"},{"name":"Bucket Sort","path":"Bucket Sort","contentType":"directory"},{"name":"Comb Sort","path":"Comb Sort","contentType":"directory"},{"name":"Combinatorics","path":"Combinatorics","contentType":"directory"},{"name":"Convex Hull","path":"Convex Hull","contentType":"directory"},{"name":"Count Occurrences","path":"Count Occurrences","contentType":"directory"},{"name":"Counting Sort","path":"Counting Sort","contentType":"directory"},{"name":"Depth-First Search","path":"Depth-First Search","contentType":"directory"},{"name":"Deque","path":"Deque","contentType":"directory"},{"name":"Dijkstra Algorithm","path":"Dijkstra Algorithm","contentType":"directory"},{"name":"DiningPhilosophers","path":"DiningPhilosophers","contentType":"directory"},{"name":"Egg Drop Problem","path":"Egg Drop Problem","contentType":"directory"},{"name":"Encode and Decode Tree","path":"Encode and Decode Tree","contentType":"directory"},{"name":"Fixed Size Array","path":"Fixed Size Array","contentType":"directory"},{"name":"Fizz Buzz","path":"Fizz Buzz","contentType":"directory"},{"name":"GCD","path":"GCD","contentType":"directory"},{"name":"Graph","path":"Graph","contentType":"directory"},{"name":"Hash Set","path":"Hash Set","contentType":"directory"},{"name":"Hash Table","path":"Hash Table","contentType":"directory"},{"name":"Hashed Heap","path":"Hashed Heap","contentType":"directory"},{"name":"HaversineDistance","path":"HaversineDistance","contentType":"directory"},{"name":"Heap Sort","path":"Heap Sort","contentType":"directory"},{"name":"Heap","path":"Heap","contentType":"directory"},{"name":"Huffman Coding","path":"Huffman Coding","contentType":"directory"},{"name":"Images","path":"Images","contentType":"directory"},{"name":"Insertion Sort","path":"Insertion Sort","contentType":"directory"},{"name":"K-Means","path":"K-Means","contentType":"directory"},{"name":"Karatsuba Multiplication","path":"Karatsuba Multiplication","contentType":"directory"},{"name":"Knuth-Morris-Pratt","path":"Knuth-Morris-Pratt","contentType":"directory"},{"name":"Kth Largest Element","path":"Kth Largest Element","contentType":"directory"},{"name":"LRU Cache","path":"LRU Cache","contentType":"directory"},{"name":"Linear Regression","path":"Linear Regression","contentType":"directory"},{"name":"Linear Search","path":"Linear Search","contentType":"directory"},{"name":"Linked List","path":"Linked List","contentType":"directory"},{"name":"Longest Common Subsequence","path":"Longest Common Subsequence","contentType":"directory"},{"name":"Merge Sort","path":"Merge Sort","contentType":"directory"},{"name":"Miller-Rabin Primality Test","path":"Miller-Rabin Primality Test","contentType":"directory"},{"name":"Minimum Edit Distance","path":"Minimum Edit Distance","contentType":"directory"},{"name":"Minimum Spanning Tree (Unweighted)","path":"Minimum Spanning Tree (Unweighted)","contentType":"directory"},{"name":"Minimum Spanning Tree","path":"Minimum Spanning Tree","contentType":"directory"},{"name":"MinimumCoinChange","path":"MinimumCoinChange","contentType":"directory"},{"name":"Monty Hall Problem","path":"Monty Hall Problem","contentType":"directory"},{"name":"Multiset","path":"Multiset","contentType":"directory"},{"name":"Naive Bayes Classifier","path":"Naive Bayes Classifier","contentType":"directory"},{"name":"Octree","path":"Octree","contentType":"directory"},{"name":"Ordered Array","path":"Ordered Array","contentType":"directory"},{"name":"Ordered Set","path":"Ordered Set","contentType":"directory"},{"name":"Palindromes","path":"Palindromes","contentType":"directory"},{"name":"Permutations","path":"Permutations","contentType":"directory"},{"name":"Priority Queue","path":"Priority Queue","contentType":"directory"},{"name":"QuadTree","path":"QuadTree","contentType":"directory"},{"name":"Queue","path":"Queue","contentType":"directory"},{"name":"Quicksort","path":"Quicksort","contentType":"directory"},{"name":"Rabin-Karp","path":"Rabin-Karp","contentType":"directory"},{"name":"Radix Sort","path":"Radix Sort","contentType":"directory"},{"name":"Radix Tree","path":"Radix Tree","contentType":"directory"},{"name":"Red-Black Tree","path":"Red-Black Tree","contentType":"directory"},{"name":"Ring Buffer","path":"Ring Buffer","contentType":"directory"},{"name":"Rootish Array Stack","path":"Rootish Array Stack","contentType":"directory"},{"name":"Run-Length Encoding","path":"Run-Length Encoding","contentType":"directory"},{"name":"Segment Tree","path":"Segment Tree","contentType":"directory"},{"name":"Select Minimum Maximum","path":"Select Minimum Maximum","contentType":"directory"},{"name":"Selection Sampling","path":"Selection Sampling","contentType":"directory"},{"name":"Selection Sort","path":"Selection Sort","contentType":"directory"},{"name":"Set Cover (Unweighted)","path":"Set Cover (Unweighted)","contentType":"directory"},{"name":"Shell Sort","path":"Shell Sort","contentType":"directory"},{"name":"Shortest Path (Unweighted)","path":"Shortest Path (Unweighted)","contentType":"directory"},{"name":"Shuffle","path":"Shuffle","contentType":"directory"},{"name":"Shunting Yard","path":"Shunting Yard","contentType":"directory"},{"name":"Single-Source Shortest Paths (Weighted)","path":"Single-Source Shortest Paths (Weighted)","contentType":"directory"},{"name":"Singly Linked List","path":"Singly Linked List","contentType":"directory"},{"name":"Skip-List","path":"Skip-List","contentType":"directory"},{"name":"Slow Sort","path":"Slow Sort","contentType":"directory"},{"name":"Sorted Set","path":"Sorted Set","contentType":"directory"},{"name":"Splay Tree","path":"Splay Tree","contentType":"directory"},{"name":"Stack","path":"Stack","contentType":"directory"},{"name":"Strassen Matrix Multiplication","path":"Strassen Matrix Multiplication","contentType":"directory"},{"name":"Ternary Search Tree","path":"Ternary Search Tree","contentType":"directory"},{"name":"Threaded Binary Tree","path":"Threaded Binary Tree","contentType":"directory"},{"name":"Topological Sort","path":"Topological Sort","contentType":"directory"},{"name":"Treap","path":"Treap","contentType":"directory"},{"name":"Tree","path":"Tree","contentType":"directory"},{"name":"Trie","path":"Trie","contentType":"directory"},{"name":"Two-Sum Problem","path":"Two-Sum Problem","contentType":"directory"},{"name":"Union-Find","path":"Union-Find","contentType":"directory"},{"name":"Z-Algorithm","path":"Z-Algorithm","contentType":"directory"},{"name":"swift-algorithm-club.xcworkspace","path":"swift-algorithm-club.xcworkspace","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".swiftlint.yml","path":".swiftlint.yml","contentType":"file"},{"name":".travis.yml","path":".travis.yml","contentType":"file"},{"name":"Algorithm Design.markdown","path":"Algorithm Design.markdown","contentType":"file"},{"name":"Big-O Notation.markdown","path":"Big-O Notation.markdown","contentType":"file"},{"name":"LICENSE.txt","path":"LICENSE.txt","contentType":"file"},{"name":"README.markdown","path":"README.markdown","contentType":"file"},{"name":"Under Construction.markdown","path":"Under Construction.markdown","contentType":"file"},{"name":"What are Algorithms.markdown","path":"What are Algorithms.markdown","contentType":"file"},{"name":"Why Algorithms.markdown","path":"Why Algorithms.markdown","contentType":"file"},{"name":"gfm-render.sh","path":"gfm-render.sh","contentType":"file"},{"name":"install_swiftlint.sh","path":"install_swiftlint.sh","contentType":"file"}],"totalCount":114}},"fileTreeProcessingTime":74.959382,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/devatef/swift-algorithm-club/branches":{"post":"B78gAjMCpEF0pEChhLODN9URExqcr8ECnXtqXTY9EOJgvQKj5ABNX2Ebpe83lcOMcKr6NpTum5RXNacHwJ9w3w"},"/devatef/swift-algorithm-club/branches/fetch_and_merge/Permutations":{"post":"AuwbmRAhk5z-pFSLpwKOF-hK4b3CP0RD8b4Quy87J5DKxCZaIznV7cGjLEzpjeU60Y8wL_UVci0KtrVzcbxV1A"},"/devatef/swift-algorithm-club/branches/fetch_and_merge/Permutations?discard_changes=true":{"post":"IHuJeBoMYeHhIzUQHoGFv9EfUec6_F-XXfiiEXm7kQvoU7S7KRQnkN4kTddQDu6S6NqAdQ3Wafmm8AfZJzzjTw"}}},"title":"swift-algorithm-club/Two-Sum Problem at Permutations · devatef/swift-algorithm-club","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}}}