C# Algorithm Series (Part 1) Two Sum, Longest Substring Without Repeating Characters

2019年12月15日 3953点热度 0人点赞 1条评论

内容目录

Problem 1

Original link https://leetcode-cn.com/problems/two-sum/

Given an integer array nums and a target value target, please find the two integers in the array that add up to the target value and return their array indices.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9
Because nums[0] + nums[1] = 2 + 7 = 9
So return [0, 1]

Note: You cannot add the same element to itself.

Test case

[2,7,11,15]
9

Expected result

[0,1]

Format template

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
　　　　/*
　　　　Code
　　　　*/
        }
    }

Author's code, for reference only

Using brute force, run time 700ms-1100ms

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
         int [] a = new int[2];
            for (int i = 0; i < nums.Length - 1; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (nums[i] + nums[j] == target)
                    {
                        a[0] = i;
                        a[1] = j;
                    }
                }
            }
            return a;
        }
    }

Run time 400ms-600ms

Using a hash table, the drawback is that keys cannot be the same.

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
                     int[] a = new int[2];
            System.Collections.Hashtable hashtable = new System.Collections.Hashtable();
            for(int i = 0; i < nums.Length; i++)
            {
                hashtable.Add(nums[i], i);
            }
            for(int i = 0; i < nums.Length; i++)
            {
                int complement = target - nums[i];
                if (hashtable.ContainsKey(complement) && int.Parse(hashtable[complement].ToString())!=i)
                {
                    a[0] = i;
                    a[1] = int.Parse(hashtable[complement].ToString());
                }
            }
            return a;
        }
    }

Still using a hash table, the drawback is that the type stored in the hash table is object, and values need to be converted when retrieved.

        public int[] TwoSum(int[] nums, int target)
        {
            int[] a = new int[2];
            System.Collections.Hashtable h = new System.Collections.Hashtable();
            for (int i = 0; i < nums.Length; i++)
            {
                int c = target - nums[i];
                if (h.ContainsKey(c))
                {
                    a[0] = int.Parse(h.ToString()) <= nums[i] ? int.Parse(h.ToString()) : i;
                    a[1] = int.Parse(h.ToString()) > nums[i] ? int.Parse(h.ToString()) : i;
                }
                else if (!h.ContainsKey(nums[i]))
                {
                    h.Add(nums[i], i);
                }
            }
            return a;
        }

Copying someone else's work

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {
        int[] res = {0, 0};
        int len = nums.Length;
        Dictionary<int, int> dict = new Dictionary<int, int>();
        for (int i = 0; i < len; i++)
        {
            int query = target - nums[i];
            if (dict.ContainsKey(query))
            {
                int min = (i <= dict[query]) ? i : dict[query];
                int max = (i <= dict[query]) ? dict[query] : i;
                return new int[] { min, max };
            }
            else if (!dict.ContainsKey(nums[i]))
            {
                dict.Add(nums[i], i);
            }
        }
    </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> res;
}

}

---------------------

Author: Bruce- Yeung

Source: CSDN

Original text: https://blog.csdn.net/lzuacm/article/details/80551669 

Copyright statement: This article is an original piece by the blogger, please include the blog link when reprinting!

Problem Two

Original problem link https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

Given a string, please find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The longest substring without repeating characters is "abc" with length 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The longest substring without repeating characters is "b" with length 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The longest substring without repeating characters is "wke" with length 3.

Be sure to consider edge cases like empty strings, null variables, and strings with length = 1.

Test Cases

Input
" "
"au"
"abcabcbb"
"bbbbb"
"pwwkew"
"aab"

Expected results are 1,2,3,1,3,2

Code Format Template

public class Solution {
    public int LengthOfLongestSubstring(string s) {
}

}

The author's code is for reference only

Using the simplest method, around 200ms

public class Solution {
    public int LengthOfLongestSubstring(string s) {
                    if (s == null || s == "")
                return 0;
        </span><span style="color: #0000ff;">char</span>[] a = s.ToCharArray();      <span style="color: #008000;">//</span><span style="color: #008000;">Convert string to character array</span>
        <span style="color: #0000ff;">int</span> start = <span style="color: #800080;">0</span>;                   <span style="color: #008000;">//</span><span style="color: #008000;">Starting position of the interval</span>
        <span style="color: #0000ff;">int</span> stop = <span style="color: #800080;">0</span>;                    <span style="color: #008000;">//</span><span style="color: #008000;">Ending position of the interval</span>
        <span style="color: #0000ff;">int</span> newMax = <span style="color: #800080;">1</span>;                   <span style="color: #008000;">//</span><span style="color: #008000;">Current interval length</span>
        <span style="color: #0000ff;">int</span> max = <span style="color: #800080;">1</span>;                     <span style="color: #008000;">//</span><span style="color: #008000;">Maximum interval length</span>

        <span style="color: #0000ff;">for</span> (stop = <span style="color: #800080;">1</span>; stop &lt; a.Length; stop++)   <span style="color: #008000;">//</span><span style="color: #008000;">Move one position forward each time</span>

            {

bool b = false;                       //Check for duplicates

for (int i = start; i < stop; i++)  //Check if the current element has the same value in the interval

                {

if (a[stop] == a[i])        //If the character at stop+1 is found in the interval

                    {

char ls = a[stop];

if (newMax > max) max = newMax;

start = i + 1;              //Reset the start position of the interval

newMax = stop - start + 1;

b = true;

break;

}

}

if (b == false)

newMax += 1;

}

if (newMax > max) max = newMax;

return max;

}

}

Complete Test Code (Console)

using System;
namespace ConsoleApp1
{
public class Testa
{
public int LengthOfLongestSubstring(string s)
{
if (s == null || s == "")
return 0;
        </span><span style="color: #0000ff;">char</span>[] a = s.ToCharArray();      <span style="color: #008000;">//</span><span style="color: #008000;">Convert string to character array</span>
        <span style="color: #0000ff;">int</span> start = <span style="color: #800080;">0</span>;                   <span style="color: #008000;">//</span><span style="color: #008000;">Starting position of the interval</span>
        <span style="color: #0000ff;">int</span> stop = <span style="color: #800080;">0</span>;                    <span style="color: #008000;">//</span><span style="color: #008000;">Ending position of the interval</span>
        <span style="color: #0000ff;">int</span> newMax = <span style="color: #800080;">1</span>;                   <span style="color: #008000;">//</span><span style="color: #008000;">Current interval length</span>
        <span style="color: #0000ff;">int</span> max = <span style="color: #800080;">1</span>;                     <span style="color: #008000;">//</span><span style="color: #008000;">Maximum interval length</span>

        <span style="color: #0000ff;">for</span> (stop = <span style="color: #800080;">1</span>; stop &lt; a.Length; stop++)   <span style="color: #008000;">//</span><span style="color: #008000;">Move one position forward each time</span>

            {

bool b = false;                       //Check for duplicates

for (int i = start; i < stop; i++)  //Check if the current element has the same value in the interval

                {

if (a[stop] == a[i])        //If the character at stop+1 is found in the interval

                    {

char ls = a[stop];

if (newMax > max) max = newMax;

start = i + 1;              //Reset the starting position of the interval

newMax = stop - start + 1;      //Reset the interval length

b = true;

break;

}

}

if (b == false)             ////If the interval length has not been reset, increase it by 1

newMax += 1;

}

if (newMax > max) max = newMax;

return max;

}

}

class Program

{
    </span><span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span> Main(<span style="color: #0000ff;">string</span><span style="color: #000000;">[] args)
    {
        Testa t1 </span>= <span style="color: #0000ff;">new</span> Testa();                                     <span style="color: #008000;">//</span><span style="color: #008000;">Correct results</span>
        Console.WriteLine(t1.LengthOfLongestSubstring(<span style="color: #800000;">"</span> <span style="color: #800000;">"</span>));       <span style="colo


            Console.WriteLine(t1.LengthOfLongestSubstring("au"));       // 2
            Console.WriteLine(t1.LengthOfLongestSubstring("abcabcbb")); // 3
            Console.WriteLine(t1.LengthOfLongestSubstring("bbbbb"));    // 1
            Console.WriteLine(t1.LengthOfLongestSubstring("pwwkew"));   // 3
            Console.WriteLine(t1.LengthOfLongestSubstring("aab"));      // 2
            
            Console.ReadKey();
        }
    }
}

使用哈希集合，速度更快，100ms-150ms

        public int LengthOfLongestSubstring(string s)
        {
            int n = s.Length;
            HashSet<char> set = new HashSet<char>();        // 集合
            int ans = 0, start = 0, stop = 0;               // ans为字符串长度，start区间起点，stop区间终点
            while (start < n && stop < n)
            {
                // try to extend the range [i, j]
                if (!set.Contains(s[stop]))
                {
                    set.Add(s[stop++]);
                    ans = Math.Max(ans, stop - start);
                    // 或者ans = ans > (stop - start) ? ans : (stop - start)
                }
                else
                {
                    set.Remove(s[start++]);
                }
            }
            return ans;
        }

完整控制台测试代码

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp2
{
    public class Solution
    {
        public int LengthOfLongestSubstring(string s)
        {
            int n = s.Length;
            HashSet<char> set = new HashSet<char>();        // 集合
            int ans = 0, start = 0, stop = 0;               // ans为字符串长度，start区间起点，stop区间终点
            while (start < n && stop < n)
            {
                // try to extend the range [i, j]
                if (!set.Contains(s[stop]))
                {
                    set.Add(s[stop++]);
                    ans = Math.Max(ans, stop - start);
                    // 或者ans = ans > (stop - start) ? ans : (stop - start)
                }
                else
                {
                    set.Remove(s[start++]);
                }
            }
            return ans;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Solution t1 = new Solution();                                     // 正确结果
            Console.WriteLine(t1.LengthOfLongestSubstring(""));        // 1
            Console.WriteLine(t1.LengthOfLongestSubstring("au"));       // 2
            Console.WriteLine(t1.LengthOfLongestSubstring("abcabcbb")); // 3
            Console.WriteLine(t1.LengthOfLongestSubstring("bbbbb"));    // 1
            Console.WriteLine(t1.LengthOfLongestSubstring("pwwkew"));   // 3
            Console.WriteLine(t1.LengthOfLongestSubstring("aab"));      // 2
            
            Console.ReadKey();
        }
    }
}