My AC code using hash,how can I improve it?


  • 0
    J
    class Solution {
    public:
            //mod ;dealing with negetive remainer;
    	int posMod(int i, int mod){
    		int t = i%mod;
    		if (t < 0) return t + mod;
    		else return t;
    	}
    	vector<int> twoSum(vector<int> &numbers, int target) {
    		const int mod = 997;
    		vector<vector<int> > ht(mod);
    		int n = numbers.size();
    
                    //hash,store the index;
    		for (int i = 0; i < n; ++i){
    			ht[posMod(numbers[i], mod)].push_back(i);
    		}
    		for (int i = 0; i<mod; ++i){
    			int j = posMod(target-i,mod);
    			for (int m = 0; m < ht[i].size(); ++m){
    				for (int n = 0; n < ht[j].size(); ++n){
    				        int i1=ht[i][m],i2=ht[j][n];
    					if (i1!=i2 && target == (numbers[i1] + numbers[i2])){
    						vector<int> result(2);
    						result[0] = i1 + 1;
    						result[1] = i2 + 1;
    						if (result[0]>result[1]) swap(result[0], result[1]);
    						return result;
    					}
    				}
    			}
    
    		}
    	}
    };

Log in to reply
 

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