LeetCode 1.两数之和

53 阅读 0 评论 35 点赞

我是靠谱客的博主妩媚眼神，最近开发中收集的这篇文章主要介绍LeetCode 1.两数之和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这个题其实别看他简单，要实现O(n)的复杂度就有点意思了

第一种解法：当然是大家都会的暴力解法

时间复杂度O(n^2) 空间复杂度O(1)

java描述：

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

        int[] two = new int[2];

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

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

                if (nums[i] + nums[j] == target){

                    two[0] = i;

                    two[1] = j;

                }

            }

        }

        return two;

    }

javaScript描述：

var twoSum = function(nums, target) {

    let two = [];

    for(let i = 0; i < nums.length - 1; i++) {

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

            if(nums[i] + nums[j] === target) {

                two[0] = i;

                two[1] = j;

            }

        }

    }

    return two;

};

第二种解法：空间换时间的思想，用hash表

时间复杂度O(n) 空间复杂度O(n)

java描述：

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

        int[] result = new int[2];

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

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

            if (map.containsKey(target - nums[i])) {

                result[1] = i;

                result[0] = map.get(target - nums[i]);

            }

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

        }

        return result;

    }

C++描述：

vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> result;

        unordered_map<int, int> map;

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

            if (map.find(target - nums[i]) != map.end()) {

                result.push_back(map[target - nums[i]]);

                result.push_back(i);

            }

            map[nums[i]] = i;

        }

        return result;

    }

javaScript描述：

var twoSum = function(nums, target) {

    const map = {}

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

        let another = target - nums[i];

        if(another in map) {

            return [map[another], i]

        }

        map[nums[i]] = i;

    }

    return map;

};