[LeetCode] 1. 2 つの合計

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

簡単

整数の配列が与えられた場合 数字 そして整数 ターゲット、戻る 合計が次のようになる 2 つの数値のインデックス ターゲット.

各入力には次のものがあると想定できます。 その通り 1つの解決策を使用することはできません。同じ要素を 2 回実行します。

回答は任意の順序で返すことができます。

例 1:

入力： 数値 = [2,7,11,15]、ターゲット = 9
出力： [0,1]
説明： nums[0] + nums[1] == 9 であるため、[0, 1] を返します。

例 2:

入力： 数値 = [3,2,4]、ターゲット = 6
出力： [1,2]

例 3:

入力： 数値 = [3,3]、ターゲット = 6
出力： [0,1]

制約:

2 <= nums.length <= 10 ⁴
-10 ⁹ <= nums[i] <= 10 ⁹
-10 ⁹ <= ターゲット <= 10 ⁹
有効な答えは 1 つだけ存在します。

フォローアップ： 以下のアルゴリズムを思いつきませんか? O(n ² ) 時間の複雑さ?

パイソン

				
					import List # ブルートフォース # 時間計算量: O(n^2) # 空間計算量: O(1) クラス 解決策: def twoSum(self, nums: List[int], target: int) -> List[int] : for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[j] == target - nums[i]: return [i, j] # hashMap #時間計算量: O(n) # 空間計算量: O(1) クラス Solution(object): def twoSum(self, nums: List[int], target: int) -> List[int]: numMap = {} for i 、 enumerate(nums) の数値: 補数 = ターゲット - numMap の補数の場合の数値: return [numMap[complement], i] numMap[num] = i return [] # 2 ポインター # 時間計算量: O(n) # 空間計算量: O(1) クラス Solution(object): def twoSum(self, nums: List[int], target: int) -> List[List[int]]: res = [] left, right = 0, len(nums ) - 1 while (left < right): currSum = nums[left] + nums[right] if currSum < target または (left > 0 and nums[left] == nums[left - 1]): left += 1 elif currSum > target or (right < len(nums)-1 and nums[right] == nums[right + 1]): right -= 1 else: res.append([nums[left], nums[ right]]) left += 1 right -= 1 return res nums = [2, 7, 11, 15] target = 9 solution = Solution() result = solution.twoSum(nums, target) print(result)

簡単

パイソン

関連記事