LeetCode 第1题

题目

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路

思路非常简单,就是把要找的数字target,减去第一个的差,是否等于第二个数

如果是,返回这两个数的下标,如果不是,循环继续。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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[j] == target - nums[i]) {
                    return new int[] { i , j };
                }
            }
        }
        return null;
    }
}

第一层循环取第一个数i,然后进入第二层循环,

第二层循环从第二个数j 开始,判断要找的数-第一个数i 的差 是否等于 第二个数 j

如果不是第二层取第三个数,再进行比较。

如果第二层遍历完还没结果说明第一层的第一个数i不对,所以第一层取第二个数

再次进入第二层依次遍历。

当差等于第二层的某个数的时候,说明找到了,返回i和j的下标。

时间复杂度:O(n)

空间复杂度:O(n)