题目

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

方法一: 暴力枚举

思路

通过枚举数组中的每一个数，组合来查找是否有适合target的两个整数

设两个数分别是x , y,他们的下标是i , j

两个循环，第一个找一个x，x前面的数都和x匹配过了，所以只需要去找x后面的数，即从j=i+1开始找y

找到了x和y就可以将两个下标输出

代码实现

//暴力枚举找出两数之和

public class test {
    public static void main(String[] args) {
        int nums[] = new int[]{2, 7, 11, 15};
        int target = 17 ;
        int[] result = new Solution().twoSum(nums, target);
        for (int i : result) {
            System.out.println(i + "");
        }
    }
}
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;                     //获取数组长度
        for (int i = 0; i < n - 1; ++i) {        //x只要找到倒数第二个，后面的会和x匹配
            for (int j = i + 1; j < n; ++j) {    //i的前面不用去考虑，考虑i后面的
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

输出结果：

0
3

算法主体

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;                     //获取数组长度
        for (int i = 0; i < n - 1; ++i) {        //x只要找到倒数第二个，后面的会和x匹配
            for (int j = i + 1; j < n; ++j) {    //i的前面不用去考虑，考虑i后面的
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

C

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for (int i = 0; i < numsSize; ++i) {
        for (int j = i + 1; j < numsSize; ++j) {
            if (nums[i] + nums[j] == target) {
                int* ret = malloc(sizeof(int) * 2);
                ret[0] = i, ret[1] = j;
                *returnSize = 2;
                return ret;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

复杂度

时间复杂度：O(N^2^)，最坏情况下数组中任意两个数都要进行匹配

空间复杂度：O(1)

对于这种情况，一般用空间去换时间，所以要进行一下优化

方法二: 哈希表

思路

创建一个哈希表，先将数组第一个数存进去，并从第二个元素开始查找，让target - nums[i]与存放在哈希表中的key匹配，没有匹配的就存进哈希表中，如果匹配成功就输出这两个元素及下标

哈希表思路

代码实现

//哈希表
import java.util.HashMap;
import java.util.Map;

public class test {
    public static void main(String[] args) {
        int nums[] = new int[]{2, 7, 11, 15};
        int target = 18;
        int[] result = new Solution().twoSum(nums, target);
        for (int i : result) {
            System.out.println(i + "");

        }
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;

        //初始化哈希表，指定哈希表的容量以防止哈希表扩容带来性能的消耗
        //这里指定哈希表的容量为len-1，是因为最后一个元素全部比较过了
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>(len -1 );
        hashtable.put(nums[0], 0);
        for (int i = 1; i < len; i++) {  //从第二个开始比较
            int another = target -nums[i];
            if (hashtable.containsKey(another)) {		//寻找有没有key与another对应
                return new int[]{hashtable.get(another), i};	//找到，返回值和下标
            }
            hashtable.put(nums[i], i);		//没有匹配，存入哈希表中
        }
        return new int[0];
    }
}

输出结果：

1
2

算法主体

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;

        //初始化哈希表，指定哈希表的容量以防止哈希表扩容带来性能的消耗
        //这里指定哈希表的容量为len-1，是因为最后一个元素全部比较过了
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>(len -1 );
        hashtable.put(nums[0], 0);
        for (int i = 1; i < len; i++) {  //从第二个开始比较
            int another = target -nums[i];
            if (hashtable.containsKey(another)) {		//寻找有没有key与another对应
                return new int[]{hashtable.get(another), i};	//找到，返回值和下标
            }
            hashtable.put(nums[i], i);		//没有匹配，存入哈希表中
        }
        return new int[0];
    }
}

C

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        it->val = ival;
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);
        if (it != NULL) {
            int* ret = malloc(sizeof(int) * 2);
            ret[0] = it->val, ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}