LeetCode解法从慢到快——1.Two Sum

作者: KaelQ | 来源:发表于2017-08-15 16:40 被阅读458次
    • 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]. 
      
    • Tips:
      1.可能会有两个相同的数字。
      2.注意有负数。

    1.最容易想到的解法

    • 冒泡查询到目标数字,找出位数,返回即可。
      代码如下:
      public int[] twoSumOne(int[] nums, int target) {
        int[] result = new int[2];
        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;
                    return result;
                }
            }
        }
        return null;
      }
      
      运行结果:
      Runtime: 39 ms
      Beats: 30.80%
      时间复杂度:O(n^2)
      空间复杂度:O(1)

    2. 第二种进阶方法

    • 先快速排序数组,然后将i和i+1相加,取刚好大于target的两数,然后进行两个循环,小数和其后的所有数进行相加寻找target-小数,大数和其前的所有数进行相加寻找target-大数。
      public int[] twoSumTwo(int[] nums, int target) {
        int[] result = new int[2];
        ArrayList<Integer> numsSort = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            numsSort.add(nums[i]);
        }
        Arrays.sort(nums);
        int[] resultNum = new int[2];
        int small = -1;
        int large = -1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] + nums[i + 1] == target) {
                resultNum[0] = nums[i];
                resultNum[1] = nums[i + 1];
            } else if (nums[i] + nums[i + 1] > target) {
                small = i;
                large = i + 1;
            }
        }
        if (small != -1 || large != -1) {
            for (int i = 0; i < large; i++) {
                if (nums[i] + nums[large] == target) {
                    resultNum[0] = nums[i];
                    resultNum[1] = nums[large];
                }
            }
      
            for (int i = nums.length - 1; i > small; i--) {
                if (nums[i] + nums[small] == target) {
                    resultNum[0] = nums[small];
                    resultNum[1] = nums[i];
                }
            }
        }
      
        for (int i = 0; i < numsSort.size(); i++) {
            if (numsSort.get(i) == resultNum[0] && result[0] == 0) {
                result[0] = i;
            } else if (numsSort.get(i) == resultNum[1] && result[1] == 0) {
                result[1] = i;
            }
        }
        return result;
      }
      
      public int[] quickSort(int[] array, int begin, int end) {
        if (array == null || begin < end) {
            int p = patition(array, begin, end);
            quickSort(array, begin, p - 1);
            quickSort(array, p + 1, end);
        }
        return array;
      }
      
      private int patition(int[] array, int begin, int end) {
        int key = array[begin];
        while (begin < end) {
            while (begin < end && array[end] >= key) {
                end--;
            }
            array[begin] = array[end];
            while (begin < end && array[begin] < key) {
                begin++;
            }
            array[end] = array[begin];
        }
        array[begin] = key;
        return begin;
      }
      
      结果:出现了两个问题
      1. 使用快排后堆栈溢出。
      2. 当nums为负数的时候,无法得到其中转折处数字。

    3. 使用哈希列表

    • 首先将所有元素和index放入hashmap中,然后循环数组,每次去找target-nums[i]是否在hashmap中。找到后返回i和hashmap中的index。
      public int[] twoSumThree(int[] nums, int target) {
        Map<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 other = target - nums[i];
            if (map.containsKey(other) && map.get(other) != i) {
                return new int[]{i, map.get(other)};
            }
        }
        throw new IllegalArgumentException("No two sum solution");
      }
      
      Runtime:10 ms
      Beats:56.03%
      时间复杂度:O(n)
      空间复杂度:O(n)
      将此算法优化,将两个循环归为一个循环,并且不做i的判断。
      public int[] twoSumFour(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
      }
      
      Runtime:8 ms
      Beats:76.25%
      时间复杂度:O(n)
      空间复杂度:O(n)

    4. 2方法的进阶优化

    • 使用arrays.sort方法进行快排,然后首位之和大于target则尾部index减1,小于target则首位index加1。这样找到和刚好与target相等的数字,循环后找到index数组。

      public int[] twoSumFive(int[] nums, int target) {
            int[] result = new int[2];
            int[] copyNum = new int[nums.length];
            for (int i = 0; i < copyNum.length; i++) {
                copyNum[i] = nums[i];
            }
            Arrays.sort(copyNum);
            int left = 0;
            int right = copyNum.length - 1;
            while (left < right) {
                int sum = copyNum[left] + copyNum[right];
                if (sum == target) {
                    break;
                } else if (sum > target) {
                    right--;
                } else {
                    left++;
                }
            }
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == copyNum[left]) {
                    result[0] = i;
                }
            }
            for (int i = nums.length - 1; i >= 0; i--) {
                if (nums[i] == copyNum[right]) {
                    result[1] = i;
                }
            }
            return result;
        }
      

      Runtime:6ms
      Beats:98.91%

      针对该方法再次进行优化
      首先复制数组使用Arrays.copyOf()
      将两次循环摘出来一个函数。

       public int[] twoSumSix(int[] nums, int target) {
            int[] sortNums = Arrays.copyOf(nums, nums.length);
            Arrays.sort(sortNums);
            int i = 0;
            int j = sortNums.length - 1;
      
            while (i < j) {
                if (sortNums[i] + sortNums[j] == target) {
                    return twoIndexes(sortNums[i], sortNums[j], nums);
                } else if (sortNums[i] + sortNums[j] > target) {
                    j--;
                } else {
                    i++;
                }
            }
            return new int[2];
      
        }
      
        public int[] twoIndexes(int num1, int num2, int[] nums) {
            int[] res = new int[2];
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == num1 || nums[i] == num2) {
                    res[count] = i;
                    count++;
                }
            }
            return res;
        }
      

      Runtime:5ms

    5. 最快的方法

    • 投机取巧,首先,知道数列中最大的数字。20050
      知道数列中最大的负数。size=5。
      以最大的数字为下标去申请数组空间。
      public int[] twoSumEight(int[] nums, int target) {
        int[] map = new int[20050];
        int size = 5;
        for (int i = 0; i < nums.length; i++) {
            map[nums[i] + size] = (i + 1);
            int diff = target - nums[i + 1] + size;
            if (diff < 0) continue;
            int d = map[diff];
            if (d > 0)
                return new int[]{d - 1, i + 1};
        }
        return null;
      }
      
      Runtime:3ms

    6.总结

    • 两数运算得一数时。
      1. 冒泡 初级并且低效。
      2. 哈希表。
      3. 排序后首尾缩小得到两数。
      4. 知道最大数,使用数组下标最快。

    相关文章

      网友评论

        本文标题:LeetCode解法从慢到快——1.Two Sum

        本文链接:https://www.haomeiwen.com/subject/lgtvrxtx.html