Problem: 1. 两数之和

[TOC]

题目如下：

两数之和

思路

看到这一题我首先想到的就是通过类似于冒泡排序的思想，通过两个for循环对数组里面的值进行一一相加并跟target进行比较，如果值等于target那么就返回，否则就进行下一次循环，也就是所谓的暴力解法，不过这样真的非常损耗时间复杂度

解题方法

这里面要注意的是，同一个数x不能进行重复相加，那么就需要我们进行一一枚举，即在数组nums中寻找中有没有一个数是target - x，且当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。如果找到了这个target - x则返回x和target - x的下标index即可

代码

复杂度

  • 时间复杂度:

    $O(N2)$

  • 空间复杂度:

    $O(1)$

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    return new int[]{i,j};
                }
            }
        }
         return new int[0];
    }
}