zl程序教程

您现在的位置是:首页 >  其他

当前栏目

Leetcode Two Sum

LeetCode sum two
2023-09-11 14:20:59 时间
struct Node{
    int index;
    int value;
};

bool compare(Node a, Node b)
{
    return a.value < b.value;
}

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        
        
        int i = 0;
        int size = numbers.size();
        int index2 = 0;
        
        vector<Node> nodes;
        vector<int> result;
        
        
        for(i = 0; i < size; i++){
            Node temp;
            temp.index = i + 1;
            temp.value = numbers[i];
            nodes.push_back(temp);
        }
        
        sort(nodes.begin(), nodes.end(), compare);
       
       
        for(i = 0; i < size - 1; i++){
            index2 = bSearch(nodes, target - nodes[i].value, i + 1, size);
            if(index2 != -1){
                if(nodes[i].index > nodes[index2].index){
                    result.push_back(nodes[index2].index);
                    result.push_back(nodes[i].index);
                } else {
                    result.push_back(nodes[i].index);
                    result.push_back(nodes[index2].index);
                }
              
                break;
            }
        }
        return result;
    }
    
    
    int bSearch(vector<Node> &nodes, int target, int start, int end){
        
       int mid = 0; 
       while(start <= end){
           mid = (start + end) >> 1;
           if(target < nodes[mid].value){
               end = mid - 1;
           } else if (target > nodes[mid].value){
               start = mid + 1;
           } else {
               return mid;
           }
       }
       
       return -1; 
    }
    
};