[LeetCode] 1. Two Sum ☆

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：最直接最笨的办法，遍历数组中的每一个数，从它之后的数中寻找是否有满足条件的，找到后跳出循环并返回。由于需要两次遍历，时间复杂度为O(n²)，空间复杂度为O(1)。

public class Solution {

    public int[] twoSum(int[] nums, int target) {int result[] = new int[]{-1, -1};

        for (int i = 0; i < nums.length; i++) {

            for (int j = i + 1; j < nums.length; j ++) {

                if (nums[i] + nums[j] == target) {

                    result[0] = i;

                    result[1] = j;

                    break;

                }

            }

            if ((result[0] != -1) && (result[1] != -1)) {

                break;

            }

        }

        return result;

    }

}

解法2-1：先遍历一遍数组，将每个数字存到hash表中，然后再遍历一遍，查找符合要求的数。由于存储和遍历的操作时间复杂度都是O(n)，所以总体时间复杂度为O(n)，而空间复杂度为O(n)。

public class Solution {

    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer, Integer> numHash = new HashMap<>();

        int result[] = new int[2];

        for (int i = 0; i < nums.length; i++) {

            numHash.put(nums[i], i);

        }

        for (int i = 0; i < nums.length; i++) {

            int other = target - nums[i];

            if (numHash.containsKey(other) && numHash.get(other) != i) {

                result[0] = i;

                result[1] = numHash.get(other);

                break;

            }

        }

        return result;

    }

}

解法2-2：将2-1的两次循环合并，每次先判断hashmap中是否有满足条件的数，没有的话再将当前数写入hashmap中，进行下一次循环。

public class Solution {

    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer, Integer> numHash = new HashMap<>();

        int result[] = new int[2];

        for (int i = 0; i < nums.length; i++) {

            int other = target - nums[i];

            if (numHash.containsKey(other)) {

                result[0] = i;

                result[1] = numHash.get(other);

                break;

            }

            numHash.put(nums[i], i);

        }

        return result;

    }

}

解法3: 先将数组拷贝(O(n))后采用Arrays.sort()方法进行排序，排序的时间复杂度为O(nlogn)。然后采用二分搜索法查找(O(n))，最后将找出的结果在原数组中查找其下标(O(n))，所以整体时间复杂度为(O(nlogn))。

public class Solution {

    public int[] twoSum(int[] nums, int target) {

        int[] result = new int[2];

        int[] copyList = new int[nums.length];

        System.arraycopy(nums, 0, copyList, 0, nums.length);

        Arrays.sort(copyList);

        int low = 0;

        int high = copyList.length - 1;

        while(low < high) {

            if (copyList[low] + copyList[high] < target) {

                low++;

            } else if (copyList[low] + copyList[high] > target) {

                high--;

            } else {

                result[0] = copyList[low];

                result[1] = copyList[high];

                break;

            }

        }

        int index1 = -1;

        int index2 = -1;

        for (int i = 0; i < nums.length; i++) {

            if ((index1 == -1) && (nums[i] == result[0])) {

                index1 = i;

            } else if ((index2 == -1) && (nums[i] == result[1])) {

                index2 = i;

            }

        }

        result[0] = index1;

        result[1] = index2;

        Arrays.sort(result);

        return result;

    }

}

巴特西

[LeetCode] 1. Two Sum ☆

最新文章

热门文章