两数之和

C++ 解法, 执行用时: 0ms, 内存消耗: 8556KB, 提交时间: 2015-01-29

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        map<int, int> mymap;
	vector<int> re;
	int i;
	for (i = 0; i < numbers.size(); ++i) {
		mymap[numbers[i]] = i+1;
	}
	
	
	for (i = 0; i < numbers.size(); ++i) {
		int a = numbers[i];
		int b = target - a;
		map<int, int>::iterator map_it = mymap.begin();
		map_it = mymap.find(b);
		if (map_it != mymap.end()) {
			int index1 = i+1;
			int index2 = map_it->second;
			if (index1 < index2) {
				re.push_back(index1);
				re.push_back(index2);
			} else if(index1 > index2) {
				re.push_back(index2);
				re.push_back(index2);
			} else {
				continue;
			}
			break;
		}
	}
	return re;
    }
};

C++ 解法, 执行用时: 18ms, 内存消耗: 4052KB, 提交时间: 2022-06-11

static const auto io_sync_off = [](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
//     std::cout.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    /**
     *
     * @param numbers int整型vector
     * @param target int整型
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        // write code here
        if(numbers.size() <= 2) return {1,2};
         
        vector<int> res;
//         map<int, int> hash;
//         for(int i=0; i<numbers.size(); i++){
// //             if(numbers[i] > target) continue;//ni may be negative
//             int key = target - numbers[i];
//             if(hash.find(key) == hash.end()){
//                 hash[numbers[i]] = i+1;
//             }else{
//                 res.push_back(hash[key]);
//                 res.push_back(i+1);
//                 break;
//             }
//         }
        int n=numbers.size();
        for(int i=0;i<n-1;i++){
            if(numbers[i]<=target){
                for(int j=i+1;j<n;j++){
                    if(numbers[i]+numbers[j]==target){
                        res.push_back(i+1);
                        res.push_back(j+1);
                    }
                }
            }
        }
        return res;
    }
};

C++ 解法, 执行用时: 19ms, 内存消耗: 3988KB, 提交时间: 2022-06-18

static const auto io_sync_off = [](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
//     std::cout.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    /**
     *
     * @param numbers int整型vector
     * @param target int整型
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        // write code here
        if(numbers.size() <= 2) return {1,2};
          
        vector<int> res;
//         map<int, int> hash;
//         for(int i=0; i<numbers.size(); i++){
// //             if(numbers[i] > target) continue;//ni may be negative
//             int key = target - numbers[i];
//             if(hash.find(key) == hash.end()){
//                 hash[numbers[i]] = i+1;
//             }else{
//                 res.push_back(hash[key]);
//                 res.push_back(i+1);
//                 break;
//             }
//         }
        int n=numbers.size();
        for(int i=0;i<n-1;i++){
            if(numbers[i]<=target){
                for(int j=i+1;j<n;j++){
                    if(numbers[i]+numbers[j]==target){
                        res.push_back(i+1);
                        res.push_back(j+1);
                    }
                }
            }
        }
        return res;
    }
};

C++ 解法, 执行用时: 19ms, 内存消耗: 4108KB, 提交时间: 2022-05-10

static const auto io_sync_off = [](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
//     std::cout.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    /**
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        // write code here
        if(numbers.size() <= 2) return {1,2};
        
        vector<int> res;
//         map<int, int> hash;
//         for(int i=0; i<numbers.size(); i++){
// //             if(numbers[i] > target) continue;//ni may be negative
//             int key = target - numbers[i];
//             if(hash.find(key) == hash.end()){
//                 hash[numbers[i]] = i+1;
//             }else{
//                 res.push_back(hash[key]);
//                 res.push_back(i+1);
//                 break;
//             }
//         }
        int n=numbers.size();
        for(int i=0;i<n-1;i++){
            if(numbers[i]<=target){
                for(int j=i+1;j<n;j++){
                    if(numbers[i]+numbers[j]==target){
                        res.push_back(i+1);
                        res.push_back(j+1);
                    }
                }
            }
        }
        return res;
    }
};

Rust 解法, 执行用时: 20ms, 内存消耗: 3360KB, 提交时间: 2022-04-22

use std::collections::HashMap;

struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    * 
        * @param numbers int整型一维数组 
        * @param target int整型 
        * @return int整型一维数组
    */
    pub fn twoSum(&self, nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut helper = HashMap::with_capacity(nums.len());
        
        for i in 0..nums.len() {
            let res = target - nums[i];
            if let Some(idx) = helper.get(&res) {
                return vec![*idx, i as i32 + 1];
            }
            helper.insert(nums[i], i as i32 + 1);
        }
        
        vec![]
    }
}

详情