Leetcode: 1. Two Sum

3534 ワード

1. Two Sum
Easy
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解法1:並べ替え+両端挟み
与えられた配列は必ず秩序があるとは言っていないので,配列が非秩序であると仮定した.
1.配列を小さいものから大きいものに並べ替えて、高速配列アルゴリズム2を用いることができる.配列の先頭と末尾に各ポインタをlとr 3とする.lとrが指す数値を加算sumを得,targetと比較する.sum>targetの場合、rが指す数値が大きすぎることを示すので、rは一歩左に移動する.ループを続行します.sum

public static int[] twoSum(int[] nums, int target) {
int[] copy = Arrays.copyOfRange(nums, 0, nums.length);
Arrays.sort(nums);
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
break;
}
}
int l = -1, r = -1;
for (int i = 0; i < copy.length; i++) {
if (copy[i] == nums[left] && l == -1) {
l = i;
} else if (copy[i] == nums[right]) {
r = i;
}
}
return new int[] { l, r };
}

解法2:HashMapレコードインデックスビット
2つの数字を加算してtargetを構成できることを明らかにしたからだ.もし本当にこの2つの数が存在するならば、配列の中にその中の1つの数が存在する限り、もう1つの数は必ず配列の中の残りの数の中に存在することを説明します.したがって,配列内の各数値のインデックス位置をhashmapで記録することができる.Keyは数値そのもの、valueはインデックスビットです.これにより、配列内の値を順次巡回し、現在の値がtargetを構成する値の1つであると仮定し、mapに別の数(target-現在の値)が存在するかどうかを判断することができる.存在する場合はmapの対応するkeyの対応するvalueを返します.

public int[] twoSum(int[] nums, int target) {
        Map 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[] { i, map.get(complement) };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
}

解法3:HashMapレコードインデックスビット(最適化版)
解法2によれば,最初から配列を1回巡ってmapに数字を順次格納する必要はない.判断を遍歴しながらmapを初期化することができます.理由はtarget=a+bであれば、aを巡るときbがmapに格納されていないと、bを巡るときaも必ずその前にmapに格納されるからである.

    public int[] twoSum(int[] nums, int target) {
        Map 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);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

【UVa】11389 - The Bus Driver Problem

トランプトランプトランプアルゴリズム実現