[Leetcode]1.Two Sum

今天看到某位大神的一句话，就作为开篇寄语吧。平生不识TwoSum,刷尽LeetCode也枉然。第一题是一道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. 假定每组输入，只有一种解法，也就是返回数组是唯一的。

2. 相同的元素是不能被使用两次的

解题

解法1

因为是简单类型，所以拿过来不经过太多思考就可以给出一个最简单思路，循环遍历数据两遍，取出数字相加和目标数字比较即可得出答案。

Java Solution 1:

class Solution {

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

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

            int numOne = nums[i];

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

                if (j == i)

                    break;

                if (numOne + nums[j] == target)

                    return new int[]{i,j};

            }

        }

          return new int[]{};

    }

}

这种解题思路简单直接，但考虑到时间复杂度的话是O(n^2). 可以看到收到的报告结果。

image

Java Solution 2:

一般的思路是降低时间复杂度，就是要从空间复杂度下手，多站内存，少循环的思路。用HashMap来维护数据和Index之间的关系，从而将时间复杂度降到 O(n)

class Solution {

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

        Map<Integer,Integer> indexMap = new HashMap<Integer,Integer>();

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

            Integer index = indexMap.get(target - nums[i]);

            if (index != null)

                return new int[]{index, i};

            else

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

        }

        return new int[]{};

    }

}

这样提交后的统计结果，时间成本下降了许多

image

Phython Solution 3:

这个solution 纯是自己胡乱思考出来，说白了，把每个数组里的数字都扩展成一个 和 原数组等长的 1 * m 的数组， 需要m 个，然后相加， 再从结果中找出是目标和数字的index 就完成了。由于LeetCode 不支持numpy 所以没能提交

import numpy as np

class Solution:

    def twoSum(self, nums, target):
       #原数组
        numsm = np.array(nums)

        for num in nums:
            index1 = nums.index(num)
            #每个数据新生成的 1 * m 数组
            matrix = np.ones(nums.__len__()) * num

            a = matrix + numsm
            #get target index if exists
            if np.argwhere(a == target).size > 0:
                index2 = np.argwhere(a == target)[0][0]

        if index1 != index2:
            return [index1, index2]

        return []