Annettuna on lista, jossa on $n$ lukua, sekä luku $x$. Monellako tavalla voidaan muodostaa lukupari, jossa on kahdessa eri kohdassa listassa oleva luku ja jonka summa on enintään $x$?

Voit olettaa, että $n$ on enintään $10^5$ ja jokainen listan luku ja $x$ on kokonaisluku välillä $1 \dots 10^9$. Tavoitteena on, että algoritmin aikavaativuus on $O(n \log n)$.

Python

Toteuta tiedostoon twosum.py funktio find, joka ilmoittaa lukuparien määrän.

def find(t,x):
    # TODO

if __name__ == "__main__":
    print(find([1,2,3],4)) # 2
    print(find([5,2,4,7],10)) # 4
    print(find([1,1,1,1],2)) # 6
    print(find([1,1,1,1],1)) # 0
    print(find([8,8,1,2,5,1,9,3],9)) # 14

Java

Toteuta tiedostoon TwoSum.java metodi find, joka ilmoittaa lukuparien määrän.

public class TwoSum {
    public long find(int[] t, int x) {
        // TODO
    }

    public static void main(String[] args) {
        TwoSum t = new TwoSum();
        System.out.println(t.find(new int[] {1,2,3}, 4)); // 2
        System.out.println(t.find(new int[] {5,2,4,7}, 10)); // 4
        System.out.println(t.find(new int[] {1,1,1,1}, 2)); // 6
        System.out.println(t.find(new int[] {1,1,1,1}, 1)); // 0
        System.out.println(t.find(new int[] {8,8,1,2,5,1,9,3}, 9)); // 14
    }
}