[LeetCode] 1. Two Sum
13014 ワード
1. Two Sum
質問リンク:https://leetcode.com/problems/two-sum/
この文章を書いた理由は3Sumと4Sumの問題を解くためだ.
この問題は配列問題であり、2つの要素の合計がtargetのインデックスであることを返します.
Solution
1. Brute Force
class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i=0; i<nums.length-1; i++) {
for(int j=i+1; j<nums.length; j++) {
if(nums[i]+nums[j] == target) return new int[] {i, j};
}
}
return new int[] {};
}
}
最悪の場合,O(N^2)の時間的複雑さを持つ.説明は...省略
2. Two-pass Hash Table
ここからは3Sumと4Sumの問題を解決するジャンプボードです.
HashMapを使用して、各要素とそのインデックスをHashMapに配置し、O(1)で補符号があるかどうかを検索します.(衝突が発生しない限り、HashMapで要素を検索してO(1);衝突が発生した場合、O(N))
1. Brute Force
class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i=0; i<nums.length-1; i++) {
for(int j=i+1; j<nums.length; j++) {
if(nums[i]+nums[j] == target) return new int[] {i, j};
}
}
return new int[] {};
}
}最悪の場合,O(N^2)の時間的複雑さを持つ.説明は...省略
2. Two-pass Hash Table
ここからは3Sumと4Sumの問題を解決するジャンプボードです.
HashMapを使用して、各要素とそのインデックスをHashMapに配置し、O(1)で補符号があるかどうかを検索します.(衝突が発生しない限り、HashMapで要素を検索してO(1);衝突が発生した場合、O(N))
map.get(complement)!=i同じ要素を繰り返し使用することはできません.検索した補語が自分であるかどうかを確認します.class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++) {
map.put(nums[i], i);
}
for(int i=0; i<nums.length; i++) {
int complement = target-nums[i];
if(map.containsKey(complement) && map.get(complement)!=i)
return new int[] {map.get(complement), i};
}
return new int[] {};
}
}
3. One-pass Hash Table
2番は改良された方法で、HashMapに<要素、index>を加え、O(1)で補語があるかどうかを検索します.合計1回の反復が必要であり,O(N)の時間的複雑さがある.
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++) {
int complement = target-nums[i];
if(map.containsKey(complement))
return new int[] {map.get(complement), i};
map.put(nums[i], i);
}
return new int[] {};
}
}
Reference
この問題について([LeetCode] 1. Two Sum), 我々は、より多くの情報をここで見つけました https://velog.io/@lychee/LeetCode-1.-Two-Sumテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol