I'm playing around with different implementations for the most simple of the LeetCode problems TwoSums. I have various other ways working fine using methods like indexof, Dictionary searches, brute force, etc... and my best so far is better than 98.67% using List.IndexOf

I'm trying to implement a version with BinarySearch for comparison. It passes most tests but seems to fail when needing to sum duplicates in the first and last position and the list length is gt 2. I'm sure there are other fail conditions but I can't get past this one.

When stepping through the code it returns a negative number instead of the index when the last and first are the same value despite starting at i 1 index location.

I have to be missing something obvious but I'm just not seeing it for some reason. Maybe I'm just misunderstanding how BinarySearch works with index and length.

These pass:
{ 0, 2, 3 } target 3
result: {0, 2}

{ 3, 3 } target 6
result: { 0, 1 }

{ 0, 2, 0, 3 } target 0
result: { 0, 2 }

These fail:
{ 0, 2, 0 } target 0
expected: { 0, 2 } result: null

{ 1, 4, 1 } target 2
expected: { 0, 2 }
result: null

The code sample is verbose for now while I'm working through the issues. I'll minimize it later.

offset is used to start the search at an index higher than i
subsetLength is used to keep the search length from going outside the bounds
The n > i is just a sanity check to make sure n is a higher index value than i before returning a valid result

public int[] TwoSum(int[] nums, int target)
{
    List<int> numList = new List<int>(nums);
    for (int i = 0; i < nums.Length; i  )
    {
        int offset = i   1; 
        int subsetLength = nums.Length - offset; 
        int searchNum = target - nums[i]; 
        int n = numList.BinarySearch(offset, subsetLength, searchNum, null);
        if (n > i) 
            return new int[] { i, n };
    }
    return null;
}

CodePudding user response：

Yes, you have a special case target / 2 target / 2 == target when you check for two items each of which are target / 2:

public int[] TwoSum(int[] nums, int target) {
  // Comment out if nums is already sorted
  Array.Sort(nums);

  for (int i = 0; i < nums.Length;   i) {
    int item = nums[i];
    int toFind = target - item;

    if (toFind < nums[i])
      break;

    int index = Array.BinarySearch(nums, toFind);

    if (index >= 0) {
      if (toFind == item) {
        // Special case: two equal numbers: target / 2   target / 2 = target
        if (i < nums.Length - 1 && nums[i] == nums[i   1])
          return new int[] { i, i   1 };

        break;
      }
      else
        return new int[] { i, index };
    }
  }

  return new int[] { -1, -1 };
} 

CodePudding user response：

Just sort the list before searching it:

public int[] TwoSum(int[] nums, int target)
    {
        List<int> numList = new List<int>(nums);

        numList.Sort();

        for (int i = 0; i < nums.Length; i  )
        {
            int offset = i   1;
            int subsetLength = nums.Length - offset;
            int searchNum = target - nums[i];
            int n = numList.BinarySearch(offset, subsetLength, searchNum, null);
            if (n > i)
                return new int[] { i, n };
        }
        return null;
    }