1
1

More than 5 years have passed since last update.

# アルゴリズム1000本ノック #7. 2 Sum

Last updated at Posted at 2015-12-28

#### Problem

``````与えられた整数配列Aと1つの整数Kに対して, Aの中からその合計値がKとなるような
2つの整数を見つけ, それが先頭から何番目かを小さい順に配列の形で返却せよ.
（条件を満たす2つの整数は, 必ず配列A内に1組だけ存在するものと考えて良い）

``````

#### Solution

すべての組み合わせを総当りでチェックしていくと計算量 `O(N^2)` を要するので, 効率的な解き方が必要.

Python版コード:

``````class Solution(object):
def twoSum(self, nums, target):
m = {} # store existence of each character
for i, num in enumerate(nums):
v = target - num
if v not in m:
m[num] = i + 1
else:
return [m[v], i+1]
``````

Java版コード:

``````
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> m = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int diff = target - num;
if (m.containsKey(diff)) {
return new int[] {m.get(diff), i+1};
}
m.put(num, i+1);
}
return new int[2];
}
}
``````
1
1
0

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
1
1