Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input…

LeetCode-Two Sum

(1)O(n*m)
C++:
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> ret(2);
        for(int i=0;i<numbers.size();i++){
            int temp=target-numbers[i];
            for(int j=i+1;j<numbers.size();j++){
                if(numbers[j]==temp){
                    ret[0]=i+1;
                    ret[1]=j+1;
                    return ret;
                }
            }
        }
        return ret;
    }
};
Java:
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int[] ret=new int[2];
        if(numbers==null||numbers.length==0) return ret;
        for(int i=0;i<numbers.length;i++){
            int temp=target-numbers[i];
            for(int j=i+1;j<numbers.length;j++){
                if(numbers[j]==temp){
                    ret[0]=i+1;
                    ret[1]=j+1;
                    return ret;
                }
            }
        }
        return ret;
    }
}
(2)O(nlogn)
C++:
struct Node{
    int val;
    int index;
    Node(){}
    Node(int v,int idx):val(v),index(idx){}
};
bool compare(const Node &lhs,const Node &rhs){
    return lhs.val<rhs.val;
}
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<Node> nodes;
        vector<int>ret(2);
        for(int i=0;i<numbers.size();i++)
            nodes.push_back(Node(numbers[i],i+1));
        sort(nodes.begin(),nodes.end(),compare);
        int i=0;
        int j=nodes.size()-1;
        while(i<j){
            if(nodes[i].val+nodes[j].val==target){
                ret[0]=min(nodes[i].index,nodes[j].index);
                ret[1]=max(nodes[i].index,nodes[j].index);
                break;
            }
            else if(nodes[i].val+nodes[j].val<target) i++;
            else j--;
        }
        return ret;
    }
};
Java:
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int[] ret=new int[2];
        if(numbers==null||numbers.length==0) return ret;
        Node[] nodes=new Node[numbers.length];
        for(int i=0;i<numbers.length;i++) nodes[i]=new Node(numbers[i],i+1);
        Arrays.sort(nodes,new Comparator(){
            @Override
            public int compare(Object node1,Object node2){
                return ((Node)node1).getVal()-((Node)node2).getVal();
            }
        });
        int i=0;
        int j=nodes.length-1;
        while(i<j){
            if(nodes[i].getVal()+nodes[j].getVal()==target){
                ret[0]=Math.min(nodes[i].getIndex(),nodes[j].getIndex());
                ret[1]=Math.max(nodes[i].getIndex(),nodes[j].getIndex());
                break;
            }
            else if(nodes[i].getVal()+nodes[j].getVal()<target) i++;
            else j--;
        }
        return ret;
    }
}
class Node{
    private int val;
    private int index;
    public Node(){}
    public Node(int val,int index){
        this.val=val;
        this.index=index;
    }
    public int getVal(){
        return this.val;
    }
    public int getIndex(){
        return this.index;
    }
}
(3)O(n)
C++:
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> ret(2);
        map<int,int> m;
        for(int i=0;i<numbers.size();i++){
            if(m.find(numbers[i])==m.end()) m[target-numbers[i]]=i;
            else{
                if(m[numbers[i]]<i){
                    ret[0]=m[numbers[i]]+1;
                    ret[1]=i+1;
                }
            }
        }
        return ret;
    }
};
Java:
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int[] ret=new int[2];
        if(numbers==null||numbers.length==0) return ret;
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<numbers.length;i++){
            if(!map.containsKey(numbers[i])) map.put(target-numbers[i],i);
            else{
                int j=map.get(numbers[i]);
                if(j<i){
                    ret[0]=j+1;
                    ret[1]=i+1;
                }
            }
        } 
        return ret;
    }
}

in C++ section it should be i & j instead of i+2 and j+1