My O(n) solution in C++ (6ms)


  • 0
    M
    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            int max = nums[0];
            int min = nums[0];
            for(int i = 1; i < nums.size(); i++){
                if(nums[i] > max)
                    max = nums[i];
                if(nums[i] < min)
                    min = nums[i];
            }
            vector<int> map;
            vector<int> ind;
            map.resize(max-min+1, 0);
            ind.resize(max-min+1, 0);
            for(int i = 0; i < nums.size(); i++){
                map[nums[i]-min] = 1;
                ind[nums[i]-min] = i;
            }
            vector<int> ans;
            for(int i = 0; i < nums.size(); i++)
                if(target-nums[i]-min < map.size() 
                    && map[target-nums[i]-min] 
                    && ind[target-nums[i]-min] != i){
                    ans.push_back(i);
                    ans.push_back(ind[target-nums[i]-min]);
                    break;
                }
            return ans;
        }
    };
    

    Use 2 vector of length (max - min) to obtain a O(1) look up table.
    Time O(n) and space O(max-min)


  • 0
    A

    It will work but has limitation that if max-min in your code exceeds memory limits (say >10^7) it will fail.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.