|
| 1 | +# [1. Two Sum](https://leetcode.com/problems/two-sum) |
| 2 | + |
| 3 | + |
| 4 | + |
| 5 | +## Description |
| 6 | + |
| 7 | +<p>Given an array of integers <code>nums</code> and an integer <code>target</code>, return <em>indices of the two numbers such that they add up to <code>target</code></em>.</p> |
| 8 | + |
| 9 | +<p>You may assume that each input would have <strong><em>exactly</em> one solution</strong>, and you may not use the <em>same</em> element twice.</p> |
| 10 | + |
| 11 | +<p>You can return the answer in any order.</p> |
| 12 | + |
| 13 | +<p> </p> |
| 14 | +<p><strong class="example">Example 1:</strong></p> |
| 15 | + |
| 16 | +<pre> |
| 17 | +<strong>Input:</strong> nums = [2,7,11,15], target = 9 |
| 18 | +<strong>Output:</strong> [0,1] |
| 19 | +<strong>Explanation:</strong> Because nums[0] + nums[1] == 9, we return [0, 1]. |
| 20 | +</pre> |
| 21 | + |
| 22 | +<p><strong class="example">Example 2:</strong></p> |
| 23 | + |
| 24 | +<pre> |
| 25 | +<strong>Input:</strong> nums = [3,2,4], target = 6 |
| 26 | +<strong>Output:</strong> [1,2] |
| 27 | +</pre> |
| 28 | + |
| 29 | +<p><strong class="example">Example 3:</strong></p> |
| 30 | + |
| 31 | +<pre> |
| 32 | +<strong>Input:</strong> nums = [3,3], target = 6 |
| 33 | +<strong>Output:</strong> [0,1] |
| 34 | +</pre> |
| 35 | + |
| 36 | +<p> </p> |
| 37 | +<p><strong>Constraints:</strong></p> |
| 38 | + |
| 39 | +<ul> |
| 40 | + <li><code>2 <= nums.length <= 10<sup>4</sup></code></li> |
| 41 | + <li><code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code></li> |
| 42 | + <li><code>-10<sup>9</sup> <= target <= 10<sup>9</sup></code></li> |
| 43 | + <li><strong>Only one valid answer exists.</strong></li> |
| 44 | +</ul> |
| 45 | + |
| 46 | +<p> </p> |
| 47 | +<strong>Follow-up: </strong>Can you come up with an algorithm that is less than <code>O(n<sup>2</sup>)</code><font face="monospace"> </font>time complexity? |
| 48 | + |
| 49 | +## Solutions |
| 50 | + |
| 51 | +### Solution 1: Hash Table |
| 52 | + |
| 53 | +We can use the hash table $m$ to store the array value and the corresponding subscript. |
| 54 | + |
| 55 | +Traverse the array `nums`, when you find `target - nums[i]` in the hash table, it means that the target value is found, and the index of `target - nums[i]` and $i$ are returned. |
| 56 | + |
| 57 | +The time complexity is $O(n)$ and the space complexity is $O(n)$. Where $n$ is the length of the array `nums`. |
| 58 | + |
| 59 | +=== "Python3" |
| 60 | + |
| 61 | + ```python |
| 62 | + class Solution: |
| 63 | + def twoSum(self, nums: List[int], target: int) -> List[int]: |
| 64 | + m = {} |
| 65 | + for i, x in enumerate(nums): |
| 66 | + y = target - x |
| 67 | + if y in m: |
| 68 | + return [m[y], i] |
| 69 | + m[x] = i |
| 70 | + ``` |
| 71 | + |
| 72 | +=== "Java" |
| 73 | + |
| 74 | + ```java |
| 75 | + class Solution { |
| 76 | + public int[] twoSum(int[] nums, int target) { |
| 77 | + Map<Integer, Integer> m = new HashMap<>(); |
| 78 | + for (int i = 0;; ++i) { |
| 79 | + int x = nums[i]; |
| 80 | + int y = target - x; |
| 81 | + if (m.containsKey(y)) { |
| 82 | + return new int[] {m.get(y), i}; |
| 83 | + } |
| 84 | + m.put(x, i); |
| 85 | + } |
| 86 | + } |
| 87 | + } |
| 88 | + ``` |
| 89 | + |
| 90 | +=== "C++" |
| 91 | + |
| 92 | + ```cpp |
| 93 | + class Solution { |
| 94 | + public: |
| 95 | + vector<int> twoSum(vector<int>& nums, int target) { |
| 96 | + unordered_map<int, int> m; |
| 97 | + for (int i = 0;; ++i) { |
| 98 | + int x = nums[i]; |
| 99 | + int y = target - x; |
| 100 | + if (m.count(y)) { |
| 101 | + return {m[y], i}; |
| 102 | + } |
| 103 | + m[x] = i; |
| 104 | + } |
| 105 | + } |
| 106 | + }; |
| 107 | + ``` |
| 108 | + |
| 109 | +=== "Go" |
| 110 | + |
| 111 | + ```go |
| 112 | + func twoSum(nums []int, target int) []int { |
| 113 | + m := map[int]int{} |
| 114 | + for i := 0; ; i++ { |
| 115 | + x := nums[i] |
| 116 | + y := target - x |
| 117 | + if j, ok := m[y]; ok { |
| 118 | + return []int{j, i} |
| 119 | + } |
| 120 | + m[x] = i |
| 121 | + } |
| 122 | + } |
| 123 | + ``` |
| 124 | + |
| 125 | +=== "TypeScript" |
| 126 | + |
| 127 | + ```ts |
| 128 | + function twoSum(nums: number[], target: number): number[] { |
| 129 | + const m: Map<number, number> = new Map(); |
| 130 | + |
| 131 | + for (let i = 0; ; ++i) { |
| 132 | + const x = nums[i]; |
| 133 | + const y = target - x; |
| 134 | + |
| 135 | + if (m.has(y)) { |
| 136 | + return [m.get(y)!, i]; |
| 137 | + } |
| 138 | + |
| 139 | + m.set(x, i); |
| 140 | + } |
| 141 | + } |
| 142 | + ``` |
| 143 | + |
| 144 | +=== "Rust" |
| 145 | + |
| 146 | + ```rust |
| 147 | + use std::collections::HashMap; |
| 148 | + |
| 149 | + impl Solution { |
| 150 | + pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> { |
| 151 | + let mut map = HashMap::new(); |
| 152 | + for (i, item) in nums.iter().enumerate() { |
| 153 | + if map.contains_key(item) { |
| 154 | + return vec![i as i32, map[item]]; |
| 155 | + } else { |
| 156 | + let x = target - nums[i]; |
| 157 | + map.insert(x, i as i32); |
| 158 | + } |
| 159 | + } |
| 160 | + unreachable!() |
| 161 | + } |
| 162 | + } |
| 163 | + ``` |
| 164 | + |
| 165 | +=== "JavaScript" |
| 166 | + |
| 167 | + ```js |
| 168 | + /** |
| 169 | + * @param {number[]} nums |
| 170 | + * @param {number} target |
| 171 | + * @return {number[]} |
| 172 | + */ |
| 173 | + var twoSum = function (nums, target) { |
| 174 | + const m = new Map(); |
| 175 | + for (let i = 0; ; ++i) { |
| 176 | + const x = nums[i]; |
| 177 | + const y = target - x; |
| 178 | + if (m.has(y)) { |
| 179 | + return [m.get(y), i]; |
| 180 | + } |
| 181 | + m.set(x, i); |
| 182 | + } |
| 183 | + }; |
| 184 | + ``` |
| 185 | + |
| 186 | +=== "C#" |
| 187 | + |
| 188 | + ```cs |
| 189 | + public class Solution { |
| 190 | + public int[] TwoSum(int[] nums, int target) { |
| 191 | + var m = new Dictionary<int, int>(); |
| 192 | + for (int i = 0, j; ; ++i) { |
| 193 | + int x = nums[i]; |
| 194 | + int y = target - x; |
| 195 | + if (m.TryGetValue(y, out j)) { |
| 196 | + return new [] {j, i}; |
| 197 | + } |
| 198 | + if (!m.ContainsKey(x)) { |
| 199 | + m.Add(x, i); |
| 200 | + } |
| 201 | + } |
| 202 | + } |
| 203 | + } |
| 204 | + ``` |
| 205 | + |
| 206 | +=== "PHP" |
| 207 | + |
| 208 | + ```php |
| 209 | + class Solution { |
| 210 | + /** |
| 211 | + * @param Integer[] $nums |
| 212 | + * @param Integer $target |
| 213 | + * @return Integer[] |
| 214 | + */ |
| 215 | + function twoSum($nums, $target) { |
| 216 | + foreach ($nums as $key => $x) { |
| 217 | + $y = $target - $x; |
| 218 | + if (isset($hashtable[$y])) { |
| 219 | + return [$hashtable[$y], $key]; |
| 220 | + } |
| 221 | + $hashtable[$x] = $key; |
| 222 | + } |
| 223 | + } |
| 224 | + } |
| 225 | + ``` |
| 226 | + |
| 227 | +=== "Scala" |
| 228 | + |
| 229 | + ```scala |
| 230 | + import scala.collection.mutable |
| 231 | + |
| 232 | + object Solution { |
| 233 | + def twoSum(nums: Array[Int], target: Int): Array[Int] = { |
| 234 | + var map = new mutable.HashMap[Int, Int]() |
| 235 | + for (i <- 0 to nums.length) { |
| 236 | + if (map.contains(target - nums(i))) { |
| 237 | + return Array(map(target - nums(i)), i) |
| 238 | + } else { |
| 239 | + map += (nums(i) -> i) |
| 240 | + } |
| 241 | + } |
| 242 | + Array(0, 0) |
| 243 | + } |
| 244 | + } |
| 245 | + ``` |
| 246 | + |
| 247 | +=== "Swift" |
| 248 | + |
| 249 | + ```swift |
| 250 | + class Solution { |
| 251 | + func twoSum(_ nums: [Int], _ target: Int) -> [Int] { |
| 252 | + var m = [Int: Int]() |
| 253 | + var i = 0 |
| 254 | + while true { |
| 255 | + let x = nums[i] |
| 256 | + let y = target - nums[i] |
| 257 | + if let j = m[target - nums[i]] { |
| 258 | + return [j, i] |
| 259 | + } |
| 260 | + m[nums[i]] = i |
| 261 | + i += 1 |
| 262 | + } |
| 263 | + } |
| 264 | + } |
| 265 | + ``` |
| 266 | + |
| 267 | +=== "Ruby" |
| 268 | + |
| 269 | + ```rb |
| 270 | + # @param {Integer[]} nums |
| 271 | + # @param {Integer} target |
| 272 | + # @return {Integer[]} |
| 273 | + def two_sum(nums, target) |
| 274 | + nums.each_with_index do |x, idx| |
| 275 | + if nums.include? target - x |
| 276 | + return [idx, nums.index(target - x)] if nums.index(target - x) != idx |
| 277 | + end |
| 278 | + next |
| 279 | + end |
| 280 | + end |
| 281 | + ``` |
| 282 | + |
| 283 | +=== "Nim" |
| 284 | + |
| 285 | + ```nim |
| 286 | + import std/enumerate |
| 287 | + |
| 288 | + proc twoSum(nums: seq[int], target: int): seq[int] = |
| 289 | + var |
| 290 | + bal: int |
| 291 | + tdx: int |
| 292 | + for idx, val in enumerate(nums): |
| 293 | + bal = target - val |
| 294 | + if bal in nums: |
| 295 | + tdx = nums.find(bal) |
| 296 | + if idx != tdx: |
| 297 | + return @[idx, tdx] |
| 298 | + ``` |
| 299 | + |
| 300 | + |
| 301 | +<!-- end --> |
0 commit comments