Two sum, c++, time limit exceed. How to fix it


  • 0
    G

    #include <vector>
    using namespace std;
    class Solution {
    public:
    vector<int> twoSum(vector<int> &numbers, int target) {
    int l=numbers.size();
    vector<int> index;

        for(int i=0;i<l-1;i++){
            for(int j=i+1;j<l;j++){
                if(numbers[i]+numbers[j]==target){
                    index.push_back(i);
                    index.push_back(j);
                    return index; 
                }
            }
            
        }
     return index;  
    }
    

    };


  • 0
    Z

    I think you should use index[0] and index[1] instead of .push_back


  • 0
    L

    the algorithm's time complexity is O(n^2), will be slow if a large set is given


  • 0
    M

    I think the worst time complexity should be O(n!).


  • 0
    M

    That won't make any different, these operations would only execute at most once.


  • 0
    C

    This problem should be resolved in several steps:

    1. copy numbers to another vector<int> num --- O(n)
    2. sort vector<int> num --- O(nlogn)
    3. find 2 elements in vector<int> num whose sum is target --- O(n)
    4. get the 2 elements' index in vector<int> numbers --- O(n)
      the total complexity is still O(nlogn)

Log in to reply
 

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