# Find Sum in Array

Lets start from simple search algorithms to more advanced.

## Find Zeros `O(n)`

```
class Zeros {

    public int findZeros(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                count++;
            }
        }
        return count;
    }
}
```

## Two Sum `O(n^2)`

```
�class TwoSum {

    public int findZeroSums(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] + arr[j] == 0) {
                    count++;
                }
            }
        }
        return count;
    }
}
```

## Two Sum `O(n)`

```
class TwoSumWithHashMap {

    public int[] findSums(int[] arr, int target) {
        // iterate trough the array {0, 1, 2, -1, -2, 0, 5, 7}
        // calculate difference between value from array and target, 0 - 0 = 0
        //   if 0 is contained, return index of current and value from map (which is index of that value)
        //   else put it into map, result is the key and i (index) is the value
        Map<Integer, Integer> temp = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {
            int number = arr[i]; // 2, 7, 11, 15
            // 9 - 2 = 7 -> store 2
            // 9 - 7 = 2 -> temp contains 2, so the sum is found
            // 9 - 11 = -2
            // 9 - 15 = -6
            int difference = target - number;
            if (temp.containsKey(difference)) {
                return new int[] { temp.get(difference), i };
            }
            temp.put(number, i);
        }

        return null;
    }
}
```

## Three Sum `O(n^3)`

```
class Triplets {

    public int findZeroSums(int[] arr) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                for (int k = j + 1; k < arr.length; k++) {
                    if (arr[i] + arr[j] + arr[k] == 0) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```

## Three Sum `O(n^2logn)`

```
�class TripletsWithBinarySearch {

    public int findZeroSums(int[] arr) {
        Arrays.sort(arr); // O(n log(n))

        int count = 0;
        int length = arr.length;
        for (int i = 0; i < length - 2; i++) {
            for (int j = i + 1; j < length - 1; j++) {
                int key = -arr[i] - arr[j];
                int k = Arrays.binarySearch(arr, j + 1, length, key);
                if (k > j && arr[k] - key == 0) { // compare index of found with current position (j)
                    count++;
                }
            }
        }
        return count;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ondrej-kvasnovsky-2.gitbook.io/algorithms/finding/find-sum-in-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.