1. Two Sum两屡次之同


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.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read
the above updated description carefully.
为得一个平头数组和一个目标数target,返回跟正好等于target的片只元素的序号,这里要每个输入还来正唯一排。

深受一定一个整数数组和一个对象价,找来数组中及为目标值的简单个数。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>  hash;
        vector<int> result;
        for(int i=0;i!=nums.size();i++){
            int numsToFind = target-nums[i];
            if(hash.find(numsToFind)!=hash.end()){
                result.push_back(hash[numsToFind]);
                result.push_back(i);
                return result;
            }
            hash[nums[i]]=i;
        }
        return result;
    }
};

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            int numToFind=target-nums[i];
            if(map.containsKey(numToFind))  return new int[]{ map.get(numToFind),i};
            map.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

  1. 排序数组,二分查找,但这题材待返回解元素的序号,因而是种方式不适用
  2. 构建一个哈希map,用于保存数组元素以及它的序号,此办法遍历时间O(n),寻找时空O(1),总时间复杂度O(n),空间复杂度O(n)。

若得要每个输入才针对许同种植答案,且同样的要素不可知为再次用。

思路
立刻类似题材基本的思绪是要是逐扫描数组,对于眼前元素nums[i],扫描数组中是否留存元素target-nums[i],主要透过简单栽方法查找:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    for(int i =0;i<numsSize;i++){
        for(int j=i+1;j<numsSize;j++){
            if(nums[j]==target-nums[i]){
                nums[0]=i;
                nums[1]=j;
                return nums;
            }
        }
    }
    return nums;
}

 


 

示例:

村办练习记录

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图