C# solution using binary search


  • 0
    K
    public class Solution {
        public int[] TwoSum(int[] numbers, int target) {
            int index = 0;
            int[] a = new int[2];
            for (int i=0;i<numbers.Length;i++) {
                int complement = target - numbers[i];
                index = BinarySearch(numbers,complement);
                if (index != -1) {
                    if (i == index) {
                        a[0] = i+1;
                        a[1] = index+2;                    
                    }
                    else if (i < index) {
                        a[0] = i+1;
                        a[1] = index+1;
                    }
                    else {
                        a[0] = index+1;
                        a[1] = i+1;
                    }
                    return a;
                }
            }
            return a;
        }
        public int BinarySearch(int[] nums,int complement)
        {
            int first = 0;
            int last = nums.Length-1;
            int mid = 0;
            while (first <= last)
            {
                mid = (first+last)/2;
                if (nums[mid] == complement) return mid;
                else if (nums[mid] < complement) first = mid+1;
                else last = mid-1;
            }
            return -1;
        }
    }
    

  • 0
    S

    Its a nice attempt but though the above solution takes O(log n) in best case. It will be O(n log n) in worst case.
    E.g. assume array has 1..100 and target is 199. Binary search has to perform for each element till end.
    We can try if hybrid approach possible like O(log n) best case and O(n) worst case.


Log in to reply
 

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