Accepted C solution with binary search in 4ms


  • 6
    T
    typedef struct Node {
        int value;
        int pos;
    } Node;
    
    int cmp(const void* a, const void* b) {
        return ((Node*)a)->value - ((Node*) b)->value;
    }
    
    // recusively binary search for a node which + baseNode = target
    int* twoSumHelper(Node* nodeArr, int start_pos, int end_pos, Node* baseNode, int target) {
        int pos = (start_pos + end_pos) / 2;
        int sum = nodeArr[pos].value + baseNode->value;
        if (sum == target) {
            int* result = malloc(sizeof(int) * 2);
            result[0] = baseNode->pos;
            result[1] = nodeArr[pos].pos;
            return result;
        } else {
            if (start_pos == end_pos) {
                return NULL;
            }
            
            if (sum > target){
                return twoSumHelper(nodeArr, start_pos, pos, baseNode, target);
            } else {
                return twoSumHelper(nodeArr, pos + 1, end_pos, baseNode, target);
            }
        }
    }
     
    int* twoSum(int* nums, int numsSize, int target) {
        Node* nodeArr = malloc(sizeof(Node) * numsSize);
        int i;
        for (i = 0; i < numsSize; i++) {
            nodeArr[i] = (Node){
                .value = nums[i],
                .pos = i + 1,
            };
        }
        qsort(nodeArr, numsSize, sizeof(Node), cmp);
        int* result;
        for (i = 0; i < numsSize; i++) {
            result = twoSumHelper(nodeArr, i+1, numsSize - 1, &nodeArr[i], target);
            if (result) {
                free(nodeArr);
                
                // sort result
                if (result[0] > result[1]) {
                    result[0] = result[0] + result[1];
                    result[1] = result[0] - result[1];
                    result[0] = result[0] - result[1];
                }
                return result;
            }
        }
    }

Log in to reply
 

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